Obstructions to -colouring -free graphs
En palabras de los autores
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 .
Resultado principalEl resumen no menciona limitaciones.
Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.