On subgraphs without large components.

*(English)*Zbl 1424.05076A 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\).

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\).

Reviewer: Linda Lesniak (Kalamazoo)