×

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
PDF BibTeX XML Cite
Full Text: DOI