A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

DOI10.1016/j.jctb.2022.09.001zbMath1502.05084arXiv2201.08204OpenAlexW4295796971MaRDI QIDQ2101164

Alvaro Carbonero, Patrick Hompe, Benjamin Moore, Sophie Spirkl

Publication date: 28 November 2022

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

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

zbMATH Keywords

directed graphinduced subgraph\(\chi\)-boundedness

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (4)

Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022 ⋮ Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs ⋮ Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of \(P_4\) ⋮ Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded

Cites Work

• Unnamed Item
• Unnamed Item
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Colorful induced subgraphs
• The dichromatic number of a digraph
• Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded
• Chordal directed graphs are not \(\chi\)-bounded
• On the Chromatic Number of Subgraphs of a Given Graph
• A survey of χ‐boundedness

This page was built for publication: A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number