# zbMATH — the first resource for mathematics

On subgraphs without large components. (English) Zbl 1424.05076
A coloring of a graph is defined to be a partition of the vertex set of the graph; the number of sets in the partition is referred to as the number of colors in the coloring. The authors consider a new coloring of a graph $$G$$ and define $$\chi^\ast_k(G)$$ to be the minimum number of colors needed in a coloring of $$G$$ such that each color class induces a subgraph in which each component has order at most $$k$$. Then $$\chi^\ast_1(G)$$ is just the standard chromatic number $$\chi(G)$$.
The authors show that determining whether $$\chi^\ast_k(G)\leq k$$, that is, whether $$k$$ colors suffice is NP-complete, even for $$2$$-coloring a planar triangle-free graphs. They also introduce a related Ramsey-type problem. In particular, they define the Ramsey number $$R(a,b)$$ to be the least integer $$n$$ such that for every graph $$G$$ of order $$n$$, either $$G$$ contains an induced subgraph of order $$a$$ in which each component is of order at most $$k$$ or the complement of $$G$$ contains an induced subgraph of order $$b$$ in which each component is of order at most $$k$$. Values of $$R(a,b)$$ are determined for some small $$a$$ and $$b$$.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C55 Generalized Ramsey theory 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05D10 Ramsey theory
##### Keywords:
component; independence; graph coloring; Ramsey number
Full Text: