| Abstrakt: |
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. |
