Abstract: The Burling sequence is a sequence of triangle-free graphs of increasing chromatic number. Any graph which is an induced subgraph of a graph in this sequence is called a Burling graph. These graphs have attracted some attention because they have geometric representations and because they provide counter-examples to several conjectures about bounding the chromatic number in classes of graphs. We recall an equivalent definition of Burling graphs from the first part of this work: the graphs derived from a tree. We then give several structural properties of derived graphs.
Recommendations
- Triangle‐free graphs with large chromatic number and no induced wheel
- Burling graphs revisited. I: New characterizations
- Burling graphs revisited. III: Applications to \(\chi \)-boundedness
- 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
- Graph theory with applications
- scientific article; zbMATH DE number 1002021 (Why is no real title available?)
- Perfect graphs
- Restricted frame graphs and a conjecture of Scott
- Star-cutsets and perfect graphs
- Substitution and \(\chi\)-boundedness
- The strong perfect graph theorem
- Triangle-free intersection graphs of line segments with large chromatic number
- Triangle‐free graphs with large chromatic number and no induced wheel
Cited in
(4)
This page was built for publication: Burling graphs revisited. II: Structure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6146492)
