Planar graph coloring with forbidden subgraphs : why trees and paths are dangerous

H.J. Broersma, F.V. Fomin, J. Kratochvil, G.J. Woeginger

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    1 Citation (Scopus)

    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. We present a complete picture for the case with a single forbidden connected (induced or non-induced) subgraph. The 2-coloring problem is NP-hard if the forbidden subgraph is a tree with at least two edges, and it is polynomially solvable in all other cases. The 3-coloring problem is NP-hard if the forbidden subgraph is a path, and it is polynomially solvable in all other cases. We also derive results for several forbidden sets of cycles.
    Original languageEnglish
    Title of host publicationAlgorithm Theory - SWAT 2002 (Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, July 3-5, 2002)
    EditorsM. Penttonen, E.M. Schmidt
    Place of PublicationBerlin
    PublisherSpringer
    Pages160-169
    ISBN (Print)3-540-43866-1
    DOIs
    Publication statusPublished - 2002

    Publication series

    NameLecture Notes in Computer Science
    Volume2368
    ISSN (Print)0302-9743

    Fingerprint Dive into the research topics of 'Planar graph coloring with forbidden subgraphs : why trees and paths are dangerous'. Together they form a unique fingerprint.

    Cite this