Some Results on Chromatic Number as a Function of Triangle Count

DOI10.1137/17M115918XzbMath1407.05093arXiv1604.00438WikidataQ128193381 ScholiaQ128193381MaRDI QIDQ3122312

David G. Harris

Publication date: 20 March 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

trianglechromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

Counterexamples to a Conjecture of Harris on Hall Ratio, Independence number of graphs with a prescribed number of cliques, Dense induced bipartite subgraphs in triangle-free graphs

Cites Work

• A note on Ramsey numbers
• Coloring triangle-free graphs with fixed size
• Coloring graphs with sparse neighborhoods
• The list chromatic number of graphs with small clique number
• Triangle-free graphs with large chromatic numbers
• Dense induced bipartite subgraphs in triangle-free graphs
• Distributed coloring algorithms for triangle-free graphs
• Independence number of graphs with a prescribed number of cliques
• 1-subdivisions, the fractional chromatic number and the Hall ratio
• Bipartite Subgraphs of Triangle-Free Graphs
• A General Upper Bound on the List Chromatic Number of Locally Sparse Graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Counterexamples to a Conjecture of Harris on Hall Ratio
• Separation Choosability and Dense Bipartite Induced Subgraphs
• Graph colouring and the probabilistic method