Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653052 | Electronic Notes in Discrete Mathematics | 2006 | 7 Pages |
Abstract
Many classes of graphs where the vertex coloring problem is polynomially solvable are known, the most prominent being the class of perfect graphs. However, the list-coloring problem is NP-complete for many subclasses of perfect graphs. In this work we explore the complexity boundary between vertex coloring and list-coloring on such subclasses of perfect graphs, where the former admits polynomial-time algorithms but the latter is NP-complete. Our goal is to analyze the computational complexity of coloring problems lying “between” (from a computational complexity viewpoint) these two problems: precoloring extension, μ-coloring, and (γ, μ)-coloring.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics