Universität zu Köln

Goedgebeur, Jan ORCID: 0000-0001-8984-2463 and Schaudt, Oliver (2018). Exhaustive generation of k-critical H-free graphs. J. Graph Theory, 87 (2). S. 188 - 208. HOBOKEN: WILEY. ISSN 1097-0118

Full text not available from this repository.

Abstract

We describe an algorithm for generating all k-critical H-free graphs, based on a method of Hoang etal. (A graph G is k-critical H-free if G is H-free, k-chromatic, and every H-free proper subgraph of G is (k-1)-colorable). Using this algorithm, we prove that there are only finitely many 4-critical (P7,Ck)-free graphs, for both k=4 and k=5. We also show that there are only finitely many 4-critical (P8,C4)-free graphs. For each of these cases we also give the complete lists of critical graphs and vertex-critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3-colorability problem in the respective classes. In addition, we prove a number of characterizations for 4-critical H-free graphs when H is disconnected. Moreover, we prove that for every t, the class of 4-critical planar Pt-free graphs is finite. We also determine all 52 4-critical planar P-7-free graphs. We also prove that every P-11-free graph of girth at least five is 3-colorable, and show that this is best possible by determining the smallest 4-chromatic P-12-free graph of girth at least five. Moreover, we show that every P-14-free graph of girth at least six and every P-17-free graph of girth at least seven is 3-colorable. This strengthens results of Golovach etal.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Goedgebeur, Jan UNSPECIFIED orcid.org/0000-0001-8984-2463 UNSPECIFIED Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-198361
DOI:	10.1002/jgt.22151
Journal or Publication Title:	J. Graph Theory
Volume:	87
Number:	2
Page Range:	S. 188 - 208
Date:	2018
Publisher:	WILEY
Place of Publication:	HOBOKEN
ISSN:	1097-0118
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language COLORING GRAPHS; INDUCED PATHS Multiple languages Mathematics Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/19836