Coloring graphs characterized by a forbidden subgraph
BP2STS
Published in:
 Discrete Applied Mathematics.  Elsevier BV.  2014, vol. 180, p. 101110
English
The Coloring problem is to test whether a given graph can be colored with at most k colors for some given k, such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H as an induced subgraph is known for each fixed graph H. A natural variant is to forbid a graph H only as a subgraph. We call such graphs strongly Hfree and initiate a complexity classification of Coloring for strongly Hfree graphs. We show that Coloring is NPcomplete for strongly Hfree graphs, even for k = 3, when H contains a cycle, has maximum degree at least 5, or contains a connected component with two vertices of degree 4. We also give three conditions on a forest H of maximum degree at most 4 and with at most one vertex of degree 4 in each of its connected components, such that Coloring is NPcomplete for strongly Hfree graphs even for k = 3. Finally, we classify the computational complexity of Coloring on strongly Hfree graphs for all fixed graphs H up to seven vertices. In particular, we show that Coloring is polynomialtime solvable when H is a forest that has at most seven vertices and maximum degree at most 4.

Faculty
 Faculté des sciences économiques et sociales et du management

Department
 Département d'informatique

Language


Classification

Computer science and technology

License

Rights reserved

Open access status

bronze

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/322636
Statistics
Document views: 24
File downloads: