Substitution and \(\chi\)-boundedness

DOI10.1016/j.jctb.2013.02.004zbMath1301.05230arXiv1302.1145OpenAlexW2072408231MaRDI QIDQ461725

Maria Chudnovsky, Nicolas Trotignon, Irena Penev, Alexander D. Scott

Publication date: 13 October 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

coloringhomogeneous set\(\chi\)-bounded class

Mathematics Subject Classification ID

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

Related Items

One-three join: a graph operation and its consequences ⋮ A note on chromatic number and induced odd cycles ⋮ Graphs of bounded twin-width are quasi-polynomially \(\chi \)-bounded ⋮ Chromatic number and subtrees of graphs ⋮ Amalgams and χ-Boundedness ⋮ Subgraphs of large connectivity and chromatic number ⋮ Highly Connected Subgraphs with Large Chromatic Number ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Burling graphs revisited. II: Structure ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi\)-bounded ⋮ Isolating Highly Connected Induced Subgraphs ⋮ Square-Free Graphs with No Six-Vertex Induced Path ⋮ Coloring of \((P_5, 4\)-wheel)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs of separability at most 2
• The strong perfect graph theorem
• Even pairs in Berge graphs
• Bull-free Berge graphs are perfect
• Star-cutsets and perfect graphs
• A note on Ramsey numbers
• Induced subtrees in graphs of large chromatic number
• Induced cycles and chromatic number
• Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
• Compositions for perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• Subgraphs of large connectivity and chromatic number in graphs of large chromatic number
• Radius two trees specify χ‐bounded classes
• Radius Three Trees in Graphs with Large Chromatic Number
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Sur le coloriage des graphs