Universität zu Köln

Chudnovsky, Maria, Goedgebeur, Jan ORCID: 0000-0001-8984-2463, Schaudt, Oliver and Zhong, Mingxian ORCID: 0000-0001-5924-1296 (2020). Obstructions for three-coloring graphs without induced paths on six vertices. J. Comb. Theory Ser. B, 140. S. 45 - 84. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE. ISSN 1096-0902

Full text not available from this repository.

Abstract

We prove that there are 24 4-critical P-6-free graphs, and give the complete list. We remark that, if H is connected and not a subgraph of P-6, there are infinitely many 4-critical H-free graphs. Our result answers questions of Golovach et al. and Seymour. (C) 2019 Published by Elsevier Inc.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Chudnovsky, Maria UNSPECIFIED UNSPECIFIED UNSPECIFIED Goedgebeur, Jan UNSPECIFIED orcid.org/0000-0001-8984-2463 UNSPECIFIED Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED Zhong, Mingxian UNSPECIFIED orcid.org/0000-0001-5924-1296 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-352590
DOI:	10.1016/j.jctb.2019.04.006
Journal or Publication Title:	J. Comb. Theory Ser. B
Volume:	140
Page Range:	S. 45 - 84
Date:	2020
Publisher:	ACADEMIC PRESS INC ELSEVIER SCIENCE
Place of Publication:	SAN DIEGO
ISSN:	1096-0902
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language 3-COLORABILITY Multiple languages Mathematics Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/35259