 Author
 Jan Goedgebeur (UGent)
 Organization
 Project
 Abstract
 A graph with chromatic number k is called kchromatic. Using computational methods, we show that the smallest trianglefree 6chromatic graphs have at least 32 and at most 40 vertices. We also determine the complete set of all trianglefree 5chromatic graphs up to 24 vertices. This implies that Reed's conjecture holds for trianglefree graphs up to at least this order. We also establish that a smallest regular trianglefree 5chromatic graph has 24 vertices. Finally, we show that the smallest 5chromatic graphs of girth at least 5 have at least 29 vertices and that the smallest 4chromatic graphs of girth at least 6 have at least 25 vertices.
 Keywords
 Geometry and Topology, chromatic number, exhaustive generation, Folkman number, (maximal) trianglefree graph, Reed's conjecture
Downloads

(...).pdf
 full text (Published version)
 
 UGent only
 
 
 579.47 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU8646835
 MLA
 Goedgebeur, Jan. “On Minimal Triangle‐free 6‐chromatic Graphs.” JOURNAL OF GRAPH THEORY, vol. 93, no. 1, 2020, pp. 34–48.
 APA
 Goedgebeur, J. (2020). On minimal triangle‐free 6‐chromatic graphs. JOURNAL OF GRAPH THEORY, 93(1), 34–48.
 Chicago authordate
 Goedgebeur, Jan. 2020. “On Minimal Triangle‐free 6‐chromatic Graphs.” JOURNAL OF GRAPH THEORY 93 (1): 34–48.
 Chicago authordate (all authors)
 Goedgebeur, Jan. 2020. “On Minimal Triangle‐free 6‐chromatic Graphs.” JOURNAL OF GRAPH THEORY 93 (1): 34–48.
 Vancouver
 1.Goedgebeur J. On minimal triangle‐free 6‐chromatic graphs. JOURNAL OF GRAPH THEORY. 2020;93(1):34–48.
 IEEE
 [1]J. Goedgebeur, “On minimal triangle‐free 6‐chromatic graphs,” JOURNAL OF GRAPH THEORY, vol. 93, no. 1, pp. 34–48, 2020.
@article{8646835, abstract = {A graph with chromatic number k is called kchromatic. Using computational methods, we show that the smallest trianglefree 6chromatic graphs have at least 32 and at most 40 vertices. We also determine the complete set of all trianglefree 5chromatic graphs up to 24 vertices. This implies that Reed's conjecture holds for trianglefree graphs up to at least this order. We also establish that a smallest regular trianglefree 5chromatic graph has 24 vertices. Finally, we show that the smallest 5chromatic graphs of girth at least 5 have at least 29 vertices and that the smallest 4chromatic graphs of girth at least 6 have at least 25 vertices.}, author = {Goedgebeur, Jan}, issn = {03649024}, journal = {JOURNAL OF GRAPH THEORY}, keywords = {Geometry and Topology,chromatic number,exhaustive generation,Folkman number,(maximal) trianglefree graph,Reed's conjecture}, language = {eng}, number = {1}, pages = {3448}, title = {On minimal triangle‐free 6‐chromatic graphs}, url = {http://dx.doi.org/10.1002/jgt.22467}, volume = {93}, year = {2020}, }
 Altmetric
 View in Altmetric
 Web of Science
 Times cited: