MATHEMATICA BOHEMICA, Vol. 142, No. 1, pp. 85-111, 2017
On subgraphs without large components
Glenn G. Chappell, John Gimbel
Received February 4, 2014. First published November 21, 2016.
Abstract: We consider, for a positive integer $k$, induced subgraphs in which each component has order at most $k$. Such a subgraph is said to be $k$-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 $k$-divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for $2$-coloring a planar triangle-free graph. Lastly, we consider Ramsey-type problems where graphs or their complements with large enough order must contain a large $k$-divided subgraph. We study the asymptotic behavior of "$k$-divided Ramsey numbers". We conclude by mentioning a number of open problems.
Keywords: component; independence; graph coloring; Ramsey number
Affiliations: Glenn G. Chappell, Department of Computer Science, University of Alaska, 202 Chapman Building, 513 Ambler Lane, Fairbanks, Alaska 99775-6670, USA, e-mail: email@example.com; John Gimbel, Department of Mathematical Sciences, University of Alaska, 101 Chapman Building, 513 Ambler Lane, Fairbanks, Alaska 99775-6660, USA, e-mail: firstname.lastname@example.org