On minimal triangle-free 6-chromatic graphs

DOI10.1002/JGT.22467MaRDI QIDQ5110643zbMATH OpenOpenAlexWikidataFDO

Authors Jan Goedgebeur

Publication date 21 May 2020

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.07581

zbMATH Keywords

chromatic numberexhaustive generationFolkman numbermaximal triangle-free graphReed's conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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 the smallest regular triangle-free 5-chromatic graphs have 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.

Recommendations

• Small graphs with chromatic number 5: A computer search
• A note on Reed's conjecture for triangle-free graphs
• The list chromatic number of graphs with small clique number
• On the chromatic number of triangle-free graphs of large minimum degree
• Triangle-free graphs with large chromatic numbers

Cited in

(15)

• The size of a minimum five-chromatic \(K_ 4\)-free graph
• Chromatic vertex Folkman numbers
• On the chromatic number of (\(P_6\), diamond)-free graphs
• Questions on color-critical subgraphs
• On the structure of \(C_3\)-critical minimal 6-connected graphs
• Maximal sets of triangle-factors onv = 6m vertices
• Small graphs with chromatic number 5: A computer search
• scientific article; zbMATH DE number 1076145 (Why is no real title available?)
• scientific article; zbMATH DE number 7274124 (Why is no real title available?)
• Bounds for the smallest k-chromatic graphs of given girth
• The exponential growth of the packing chromatic number of iterated Mycielskians
• The smallest 5-chromatic tournament
• A note on Reed's conjecture for triangle-free graphs
• On some generalized vertex Folkman numbers
• On semi-transitive orientability of triangle-free graphs

This page was built for publication: On minimal triangle-free 6-chromatic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5110643)