Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult

Haitze J. Broersma, F.V. Fomin, J. Kratochvil, Gerhard Woeginger

Research output: Book/ReportReportOther research output

11 Downloads (Pure)

Abstract

We consider the problem of coloring a planar graph with the minimum number of colors such that each color class avoids one or more forbidden graphs as subgraphs. We perform a detailed study of the computational complexity of this problem.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 2003

Publication series

NameMemorandum Afdeling TW
PublisherDepartment of Applied Mathematics, University of Twente
No.1701
ISSN (Print)0169-2690

Keywords

  • MSC-05C85
  • MSC-05C15
  • IR-65886
  • EWI-3521
  • MSC-05C17

Fingerprint Dive into the research topics of 'Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult'. Together they form a unique fingerprint.

Cite this