Coloring with no 2-colored 's.
Albertson, Michael O.; Chappell, Glenn G.; Kierstead, H.A.; Kündgen, André; Ramamurthi, Radhika — 2004
The Electronic Journal of Combinatorics [electronic only]
Coloring with no 2-colored 's.
On subgraphs without large components
We consider, for a positive integer , induced subgraphs in which each component has order at most . Such a subgraph is said to be -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for -coloring...
Page 1