On coloring digraphs with forbidden induced subgraphs

DOI10.1002/JGT.22920MaRDI QIDQ6074583zbMATH OpenOpenAlexFDO

Authors

Publication date 12 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

graph coloringdirected graphsinduced subgraphsGyárfás-Sumner conjecture

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15)

Abstract: We prove a conjecture by Aboulker, Charbit and Naserasr by showing that every oriented graph in which the out-neighborhood of every vertex induces a transitive tournament can be partitioned into two acyclic induced subdigraphs. We prove multiple extensions of this result to larger classes of digraphs defined by a finite list of forbidden induced subdigraphs. We thereby resolve several special cases of an extension of the famous Gy'{a}rf'{a}s-Sumner conjecture to directed graphs by Aboulker et al.

Recommendations

• Extension of Gyárfás-Sumner conjecture to digraphs
• Coloring digraphs with forbidden cycles
• χ‐bounded families of oriented graphs
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• Decomposing and colouring some locally semicomplete digraphs

Cites work

• scientific article; zbMATH DE number 3687449 (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?)
• A survey of \(\chi\)-boundedness
• Classes of directed graphs
• Decomposing and colouring some locally semicomplete digraphs
• Extension of Gyárfás-Sumner conjecture to digraphs
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• The dichromatic number of a digraph
• Tournaments and colouring

Cited in

(9)

• \((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number
• On the structure of oriented graphs and digraphs with forbidden tournaments or cycles
• Extension of Gyárfás-Sumner conjecture to digraphs
• Four proofs of the directed Brooks' theorem
• scientific article; zbMATH DE number 4160759 (Why is no real title available?)
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• On heroes in digraphs with forbidden induced forests
• Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of \(P_4\)
• Heroes in oriented complete multipartite graphs

This page was built for publication: On coloring digraphs with forbidden induced subgraphs

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