Burling graphs revisited. III: Applications to -boundedness

DOI10.1016/J.EJC.2023.103850MaRDI QIDQ6146493zbMATH OpenOpenAlexFDO

Authors Pegah Pournajafi, Nicolas Trotignon

Publication date 5 February 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Burling sequenceunbounded chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75)

Abstract: The Burling sequence is a sequence of triangle-free graphs of unbounded chromatic number. The class of Burling graphs consists of all the induced subgraphs of the graphs of this sequence. In the first and second parts of this work, we introduced derived graphs, a class of graphs, equal to the class of Burling graphs, and proved several geometric and structural results about them. In this third part, we use those results to find some Burling and non-Burling graphs, and we see some applications of this in the theory of $chi$-boundedness. In particular, we show that several graphs, like $K_5$, some series-parallel graphs that we call necklaces, and some other graphs are not weakly pervasive.

Recommendations

• Burling graphs revisited. II: Structure
• Burling graphs revisited. I: New characterizations
• Triangle‐free graphs with large chromatic number and no induced wheel
• Burling graphs, chromatic number, and orthogonal tree-decompositions
• Burling graphs, chromatic number, and orthogonal tree-decompositions

Cites work

• A survey of -boundedness
• Burling graphs revisited. I: New characterizations
• Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors
• Graph Theory and Probability
• scientific article; zbMATH DE number 1002021 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• On graphs with no induced subdivision of \(K_4\)
• Restricted frame graphs and a conjecture of Scott
• Triangle-free intersection graphs of line segments with large chromatic number

Cited in

(3)

• Burling graphs revisited. II: Structure
• A structural description of Zykov and Blanche Descartes graphs
• Polynomial-time recognition and maximum independent set in Burling graphs

This page was built for publication: Burling graphs revisited. III: Applications to \(\chi \)-boundedness

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