On minimal triangle‐free 6‐chromatic graphs. Issue 1 (22nd July 2019)

• Record Type: Journal Article
• Authors: Goedgebeur, Jan
• Is Part Of: Journal of graph theory. Volume 93:Issue 1(2020)
• Page Start: 34
• Page End: 48
• Publication Date: 2019-07-22
• Subjects: chromatic number -- exhaustive generation -- Folkman number -- (maximal) triangle‐free graph -- Reed's conjecture; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22467
• Languages: English
• ISSNs: 0364-9024

Abstract

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.