On coloring digraphs with forbidden induced subgraphs

DOI10.1002/JGT.22920zbMATH Open1522.05142arXiv2103.04191OpenAlexW3134168121MaRDI QIDQ6074583FDOQ6074583

Authors:

Publication date: 12 October 2023

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

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.

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

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

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)

Cites Work

• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• Title not available (Why is that?)
• The dichromatic number of a digraph
• Title not available (Why is that?)
• Tournaments and colouring
• Title not available (Why is that?)
• Classes of directed graphs
• A survey of \(\chi\)-boundedness
• Extension of Gyárfás-Sumner conjecture to digraphs
• Decomposing and colouring some locally semicomplete digraphs

Cited In (9)

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

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)