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: |
|
||||||||||||
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: |
|
||||||||||||
Refereed: | Yes | ||||||||||||
URI: | http://kups.ub.uni-koeln.de/id/eprint/19836 |
Downloads
Downloads per month over past year
Altmetric
Export
Actions (login required)
View Item |