pipette
ESEspañol

Obstructions to -colouring -free graphs

Iain Beaton, Ben Cameron, Adam van Omme

Preprint

In the authors' words

A graph is -free if it has no induced subgraph isomorphic to . In 2020, Chudnovsky, Goedgebeur, Schaudt, and Zhong characterized all graphs such that there are only finitely many minimal obstructions to -colouring -free graphs. In general, the minimal obstructions to -colouring -free graphs are the -vertex-critical -free graphs, those are, the -free graphs with but for every vertex in . In this paper we complete the characterization for all by showing that there are onky finitely -vertex-critical -free graphs if and only if is an induced subgraph of for some .

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 9. arXiv. Preprint, not yet peer-reviewed.