Premium
On minimal triangle‐free 6‐chromatic graphs
Author(s) -
Goedgebeur Jan
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22467
Subject(s) - combinatorics , mathematics , chromatic scale , triangle free graph , chordal graph , discrete mathematics , graph , wheel graph , windmill graph , indifference graph , critical graph , graph homomorphism , 1 planar graph , graph power , line graph
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.