Advanced search
1 file | 579.47 KB Add to list

On minimal triangle‐free 6‐chromatic graphs

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

Downloads

  • (...).pdf
    • full text (Published version)
    • |
    • UGent only
    • |
    • PDF
    • |
    • 579.47 KB

Citation

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

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 author-date
Goedgebeur, Jan. 2020. “On Minimal Triangle‐free 6‐chromatic Graphs.” JOURNAL OF GRAPH THEORY 93 (1): 34–48.
Chicago author-date (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 k-chromatic. Using computational methods, we show that the smallest triangle-free 6-chromatic graphs have at least 32 and at most 40 vertices. We also determine the complete set of all triangle-free 5-chromatic graphs up to 24 vertices. This implies that Reed's conjecture holds for triangle-free graphs up to at least this order. We also establish that a smallest regular triangle-free 5-chromatic graph has 24 vertices. Finally, we show that the smallest 5-chromatic graphs of girth at least 5 have at least 29 vertices and that the smallest 4-chromatic graphs of girth at least 6 have at least 25 vertices.},
  author       = {Goedgebeur, Jan},
  issn         = {0364-9024},
  journal      = {JOURNAL OF GRAPH THEORY},
  keywords     = {Geometry and Topology,chromatic number,exhaustive generation,Folkman number,(maximal) triangle-free graph,Reed's conjecture},
  language     = {eng},
  number       = {1},
  pages        = {34--48},
  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: