Induced subgraphs of graphs with large chromatic number. XI. Orientations
From MaRDI portal
(Redirected from Publication:1633601)
Abstract: Fix an oriented graph H, and let G be a graph with bounded clique number and very large chromatic number. If we somehow orient its edges, must there be an induced subdigraph isomorphic to H? Kierstead and Rodl raised this question for two specific kinds of digraph H: the three-edge path, with the first and last edges both directed towards the interior; and stars (with many edges directed out and many directed in). Aboulker et al subsequently conjectured that the answer is affirmative in both cases. We give affirmative answers to both questions.
Recommendations
Cites work
- Applications of hypergraph coloring to coloring graphs not inducing certain trees
- Colorful induced subgraphs
- Graph Theory and Probability
- scientific article; zbMATH DE number 1002021 (Why is no real title available?)
- scientific article; zbMATH DE number 3891425 (Why is no real title available?)
- scientific article; zbMATH DE number 3747156 (Why is no real title available?)
- scientific article; zbMATH DE number 3480625 (Why is no real title available?)
- scientific article; zbMATH DE number 3520445 (Why is no real title available?)
- scientific article; zbMATH DE number 4183452 (Why is no real title available?)
- Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
- Induced subtrees in graphs of large chromatic number
- Radius Three Trees in Graphs with Large Chromatic Number
- Radius two trees specify χ‐bounded classes
- χ‐bounded families of oriented graphs
Cited in
(25)- A note on chromatic number and induced odd cycles
- Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
- Induced subgraphs of graphs with large chromatic number. XIII. New brooms
- Conflict-free coloring of string graphs
- Extension of Gyárfás-Sumner conjecture to digraphs
- Pure pairs. II: Excluding all subdivisions of a graph
- Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded
- Oriented expressions of graph properties
- Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
- Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
- Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
- Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case
- Restricted frame graphs and a conjecture of Scott
- Induced subgraphs of graphs with large chromatic number. I. Odd holes
- scientific article; zbMATH DE number 4144029 (Why is no real title available?)
- Heroes in orientations of chordal graphs
- On coloring digraphs with forbidden induced subgraphs
- Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P₄
- Heroes in oriented complete multipartite graphs
- The inducibility of oriented stars
- Variants of the Gyárfás-Sumner conjecture: oriented trees and rainbow paths
- On heroes in digraphs with forbidden induced forests
- \((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number
- The dichromatic number of digraphs without induced subdigraphs
- Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P₄ (extended abstract)
This page was built for publication: Induced subgraphs of graphs with large chromatic number. XI. Orientations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1633601)
