Structure and colour in triangle-free graphs

DOI10.37236/9267MaRDI QIDQ2034076zbMATH OpenOpenAlexFDO

Authors N. R. Aravind, Stijn Cambie, Wouter Cames van Batenburg, Rémi de Joannis de Verclos, Ross J. Kang, Viresh Patel

Publication date 21 June 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chromatic numberJohansson's theorem

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)

Abstract: Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $chi$ contains a rainbow independent set of size $lceilfrac12chiceil$. This is sharp up to a factor $2$. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number $chi$ contains an induced cycle of length $Omega(chilogchi)$ as $chioinfty$. Even if one only demands an induced path of length $Omega(chilogchi)$, the conclusion would be sharp up to a constant multiple. We prove it for regular girth $5$ graphs and for girth $21$ graphs. As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some $c>0$ such that for every forest $H$ on $D$ vertices, every triangle-free and induced $H$-free graph has chromatic number at most $cD/logD$. We prove this assertion with `triangle-free' replaced by `regular girth $5$'.

Review text

Summary: Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number \(\chi\) contains a rainbow independent set of size \(\lceil\frac12\chi\rceil \). This is sharp up to a factor 2. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number \(\chi\) contains an induced cycle of length \(\Omega(\chi\log\chi)\) as \(\chi\to\infty \). Even if one only demands an induced path of length \(\Omega(\chi\log\chi)\), the conclusion would be sharp up to a constant multiple. We prove it for regular girth 5 graphs and for girth 21 graphs. As a common strengthening of the induced paths form of this conjecture and of \textit{A. Johansson}'s theorem [Asymptotic choice number for triangle-free graphs. Techn. Rep. 91-5, DIMACS (1996)], we posit the existence of some \(c >0\) such that for every forest \(H\) on \(D\) vertices, every triangle-free and induced \(H\)-free graph has chromatic number at most \(c D/\log D\). We prove this assertion with `triangle-free' replaced by `regular girth 5'.

Recommendations

• Cycles in triangle-free graphs of large chromatic number
• Induced colorful trees and paths in large chromatic graphs
• Triangle-free graphs with large chromatic numbers

Cites work

• A note on Ramsey numbers
• A survey of -boundedness
• Colorful induced subgraphs
• Coloring graphs with sparse neighborhoods
• scientific article; zbMATH DE number 3747156 (Why is no real title available?)
• scientific article; zbMATH DE number 3480625 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 3205929 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Induced colorful trees and paths in large chromatic graphs
• Induced subgraphs of graphs with large chromatic number. III: Long holes
• Induced subgraphs of graphs with large chromatic number. IV: Consecutive holes
• Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
• Induced subtrees in graphs of large chromatic number
• Minors in graphs of large girth
• Nombre chromatique et plus longs chemins d'un graphe
• On the divisibility of graphs
• On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• The chromatic discrepancy of graphs
• The early evolution of the \(H\)-free process
• The size of the largest hole in a random graph
• Zur algebraischen Begründung der Graphentheorie. I

Cited in

(8)

• Coloring triangle-free graphs with fixed size
• Cycles in triangle-free graphs of large chromatic number
• Extremal triangle-free and odd-cycle-free colourings of uncountable graphs
• Colouring diamond-free graphs
• A technique for multicoloring triangle-free hexagonal graphs
• Coloring of Triangle-Free Graphs on the Double Torus
• Induced colorful trees and paths in large chromatic graphs
• scientific article; zbMATH DE number 7274066 (Why is no real title available?)

This page was built for publication: Structure and colour in triangle-free graphs

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