Advanced search
1 file | 322.13 KB

Exhaustive generation of k-critical H-free graphs

Author
Organization
Project
HPC-UGent: the central High Performance Computing infrastructure of Ghent University
Abstract
We describe an algorithm for generating all k-critical H-free graphs, based on a method of Hoang et al. 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 case 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. 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 P7-free graphs. We also prove that every P11-free graph of girth at least five is 3-colorable, and showthat this is best possible by determining the smallest 4-chromatic P12-free graph of girth at least five. Moreover, we show that every P14-free graph of girth at least six and every P17-free graph of girth at least seven is 3-colorable. This strengthens results of Golovach et al.
Keywords
Graph coloring, Critical graph, H-free graph, Graph generation, LONG INDUCED PATHS, P-5-FREE GRAPHS, COLORING GRAPHS, NP-COMPLETENESS

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 322.13 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Goedgebeur, Jan, and Oliver Schaudt. 2016. “Exhaustive Generation of K-critical H-free Graphs.” In Lecture Notes in Computer Science, 9941:109–120. Cham, Switzerland: Springer.
APA
Goedgebeur, J., & Schaudt, O. (2016). Exhaustive generation of k-critical H-free graphs. Lecture Notes in Computer Science (Vol. 9941, pp. 109–120). Presented at the 42nd International workshop on Graph-Theoretic Concepts in Computer Science (WG 2016), Cham, Switzerland: Springer.
Vancouver
1.
Goedgebeur J, Schaudt O. Exhaustive generation of k-critical H-free graphs. Lecture Notes in Computer Science. Cham, Switzerland: Springer; 2016. p. 109–20.
MLA
Goedgebeur, Jan, and Oliver Schaudt. “Exhaustive Generation of K-critical H-free Graphs.” Lecture Notes in Computer Science. Vol. 9941. Cham, Switzerland: Springer, 2016. 109–120. Print.
@inproceedings{8501930,
  abstract     = {We describe an algorithm for generating all k-critical H-free graphs, based on a method of Hoang et al. 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 case 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. 
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 P7-free graphs. We also prove that every P11-free graph of girth at least five is 3-colorable, and showthat this is best possible by determining the smallest 4-chromatic P12-free graph of girth at least five. Moreover, we show that every P14-free graph of girth at least six and every P17-free graph of girth at least seven is 3-colorable. This strengthens results of Golovach et al.},
  author       = {Goedgebeur, Jan and Schaudt, Oliver},
  booktitle    = {Lecture Notes in Computer Science},
  isbn         = {9783662535356},
  issn         = {0302-9743},
  language     = {eng},
  location     = {Istanbul, Turkey},
  pages        = {109--120},
  publisher    = {Springer},
  title        = {Exhaustive generation of k-critical H-free graphs},
  url          = {http://dx.doi.org/10.1007/978-3-662-53536-3\_10},
  volume       = {9941},
  year         = {2016},
}

Altmetric
View in Altmetric
Web of Science
Times cited: