Exhaustive generation of kcritical Hfree graphs
 Author
 Jan Goedgebeur (UGent) and Oliver Schaudt
 Organization
 Project
 HPCUGent: the central High Performance Computing infrastructure of Ghent University
 Abstract
 We describe an algorithm for generating all kcritical Hfree graphs, based on a method of Hoang et al. Using this algorithm, we prove that there are only finitely many 4critical (P7, Ck)free graphs, for both k = 4 and k = 5. We also show that there are only finitely many 4critical (P8, C4)free graphs. For each case of these cases we also give the complete lists of critical graphs and vertexcritical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3colorability problem in the respective classes. Moreover, we prove that for every t, the class of 4critical planar Ptfree graphs is finite. We also determine all 52 4critical planar P7free graphs. We also prove that every P11free graph of girth at least five is 3colorable, and showthat this is best possible by determining the smallest 4chromatic P12free graph of girth at least five. Moreover, we show that every P14free graph of girth at least six and every P17free graph of girth at least seven is 3colorable. This strengthens results of Golovach et al.
 Keywords
 Graph coloring, Critical graph, Hfree graph, Graph generation, LONG INDUCED PATHS, P5FREE GRAPHS, COLORING GRAPHS, NPCOMPLETENESS
Downloads

(...).pdf
 full text
 
 UGent only
 
 
 322.13 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU8501930
 Chicago
 Goedgebeur, Jan, and Oliver Schaudt. 2016. “Exhaustive Generation of Kcritical Hfree Graphs.” In Lecture Notes in Computer Science, 9941:109–120. Cham, Switzerland: Springer.
 APA
 Goedgebeur, J., & Schaudt, O. (2016). Exhaustive generation of kcritical Hfree graphs. Lecture Notes in Computer Science (Vol. 9941, pp. 109–120). Presented at the 42nd International workshop on GraphTheoretic Concepts in Computer Science (WG 2016), Cham, Switzerland: Springer.
 Vancouver
 1.Goedgebeur J, Schaudt O. Exhaustive generation of kcritical Hfree graphs. Lecture Notes in Computer Science. Cham, Switzerland: Springer; 2016. p. 109–20.
 MLA
 Goedgebeur, Jan, and Oliver Schaudt. “Exhaustive Generation of Kcritical Hfree 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 kcritical Hfree graphs, based on a method of Hoang et al. Using this algorithm, we prove that there are only finitely many 4critical (P7, Ck)free graphs, for both k = 4 and k = 5. We also show that there are only finitely many 4critical (P8, C4)free graphs. For each case of these cases we also give the complete lists of critical graphs and vertexcritical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3colorability problem in the respective classes. Moreover, we prove that for every t, the class of 4critical planar Ptfree graphs is finite. We also determine all 52 4critical planar P7free graphs. We also prove that every P11free graph of girth at least five is 3colorable, and showthat this is best possible by determining the smallest 4chromatic P12free graph of girth at least five. Moreover, we show that every P14free graph of girth at least six and every P17free graph of girth at least seven is 3colorable. This strengthens results of Golovach et al.}, author = {Goedgebeur, Jan and Schaudt, Oliver}, booktitle = {Lecture Notes in Computer Science}, isbn = {9783662535356}, issn = {03029743}, language = {eng}, location = {Istanbul, Turkey}, pages = {109120}, publisher = {Springer}, title = {Exhaustive generation of kcritical Hfree graphs}, url = {http://dx.doi.org/10.1007/9783662535363\_10}, volume = {9941}, year = {2016}, }
 Altmetric
 View in Altmetric
 Web of Science
 Times cited: