Heroes in orientations of chordal graphs

DOI10.1137/22M1481427MaRDI QIDQ5043055zbMATH OpenOpenAlexFDO

Authors

Publication date 27 October 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

digraphschordal graphsdichromatic numberheroes

Mathematics Subject Classification ID

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

Abstract: We characterize all digraphs $H$ such that orientations of chordal graphs with no induced copy of $H$ have bounded dichromatic number.

Recommendations

• Coloring dense digraphs
• Coloring dense digraphs
• Chordal directed graphs are not \(\chi\)-bounded
• Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded
• Tournaments and colouring

Cites work

• Chordal directed graphs are not \(\chi\)-bounded
• Coloring dense digraphs
• Coloring tournaments: from local to global
• Decomposing and colouring some locally semicomplete digraphs
• Extension of Gyárfás-Sumner conjecture to digraphs
• Heroes in orientations of chordal graphs
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• On rigid circuit graphs
• The Voting Problem
• The dichromatic number of a digraph
• Tournaments and colouring
• Two results on the digraph chromatic number

Cited in

(7)

• \((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number
• Heroes in orientations of chordal graphs
• 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
• Coloring dense digraphs
• Strict chordal digraphs viewed as graphs with distinguished edges

This page was built for publication: Heroes in orientations of chordal graphs

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