A -coloring of a graph is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The -Coloring problem asks whether a graph has a -coloring with colors. The -chromatic number of a graph , denoted …
We confirm a conjecture of Gartland and Lokshtanov : if for a hereditary graph class there exists a constant such that no member of contains a -creature as an induced subgraph or a -skinny-ladder as an induced minor, then there exists a polynomial such that every contains at …