Structure and colour in triangle-free graphs

DOI10.37236/9267zbMATH Open1466.05063arXiv1912.13328OpenAlexW3174897553MaRDI QIDQ2034076FDOQ2034076

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)

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$'.

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

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

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

zbMATH Keywords

chromatic numberJohansson's theorem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Cycles in triangle-free graphs of large chromatic number
• Colouring diamond-free graphs
• Extremal triangle-free and odd-cycle-free colourings of uncountable graphs
• Title not available (Why is that?)
• A technique for multicoloring triangle-free hexagonal graphs
• Induced colorful trees and paths in large chromatic graphs
• Coloring of Triangle-Free Graphs on the Double Torus
• Coloring triangle-free graphs with fixed size

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)