Extension of Gyárfás-Sumner conjecture to digraphs

DOI10.37236/9906MaRDI QIDQ2030749zbMATH OpenOpenAlexWikidataFDO

Authors Pierre Aboulker, Reza Naserasr, Pierre Charbit

Publication date 7 June 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

dichromatic numberdigraphsGyárfás-Sumner conjecture

Mathematics Subject Classification ID

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

Abstract: The dichromatic number of a digraph $D$ is the minimum number of colors needed to color its vertices in such a way that each color class induces an acyclic digraph. As it generalizes the notion of the chromatic number of graphs, it has been a recent center of study. In this work we look at possible extensions of Gy'arf'as-Sumner conjecture. More precisely, we propose as a conjecture a simple characterization of finite sets $mathcalF$ of digraphs such that every oriented graph with sufficiently large dichromatic number must contain a member of $mathcalF$ as an induce subdigraph. Among notable results, we prove that oriented triangle-free graphs without a directed path of length $3$ are $2$-colorable. If condition of "triangle-free" is replaced with "$K_4$-free", then we have an upper bound of $414$. We also show that an orientation of complete multipartite graph with no directed triangle is 2-colorable. To prove these results we introduce the notion of emph{nice sets} that might be of independent interest.

Review text

The dichromatic number of a digraph is the minimum number of colors needed to color its vertices in such a way that each color class induces an acyclic digraph [\textit{V. Neumann-Lara}, J. Comb. Theory, Ser. B 33, 265--270 (1982; Zbl 0506.05031)]. On the other hand, Gyárfás and Sumner conjectured that: Given two graphs \(F_1\) and \(F_2\) the class of graphs with no induced \(F_1\) or \(F_2\) has bounded chromatic number if and only if one of \(F_1\); \(F_2\) is a complete graph and the other is a forest (see [\textit{A. Gyárfás}, Zastosow. Mat. 19, No. 3--4, 413--441 (1987; Zbl 0718.05041); \textit{D. P. Sumner}, in: The theory and applications of graphs. Fourth international conference, May 6--9, 1980, Western Michigan University, Kalamazoo, Michigan. New York, NY etc.: John Wiley \& Sons. 557--576 (1981; Zbl 0476.05037)]). In this paper, the authors look for possible extensions of the Gyarfas-Sumner conjecture. In particular, they conjecture a simple characterization of sets \(F\) of three digraphs such that every digraph with suciently large dichromatic number must contain a member of \(F\) as an induced subdigraph. Regarding this, the authors prove that oriented \(K_4\)-free graphs without a directed path of length \(3\) have bounded dichromatic number, where a bound of 414 is provided. They also show that an orientation of a complete multipartite graph with no directed triangle is \(2\)-colorable. To prove these results, the authors introduce the notion of ``nice sets that might be of independent interest.

Recommendations

• χ‐bounded families of oriented graphs
• On coloring digraphs with forbidden induced subgraphs
• Dichromatic number and fractional chromatic number
• A note on coloring digraphs of large girth
• Chordal directed graphs are not \(\chi\)-bounded

Cites work

• A flow theory for the dichromatic number
• A Min-Max Theorem on Tournaments
• A note on coloring digraphs of large girth
• Applications of hypergraph coloring to coloring graphs not inducing certain trees
• Classes of directed graphs
• Colorful induced subgraphs
• Coloring dense digraphs
• Forcing large transitive subtournaments
• Graph Theory and Probability
• 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 1498519 (Why is no real title available?)
• scientific article; zbMATH DE number 3262991 (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. XI. Orientations
• List coloring digraphs
• On the structure of strong 3-quasi-transitive digraphs
• Planar digraphs of digirth four are 2-colorable
• Subdivisions in digraphs of large out-degree or large dichromatic number
• The circular chromatic number of a digraph
• The dichromatic number of a digraph
• The edge density of critical digraphs
• The minimum number of edges in 4-critical digraphs of given order
• The Voting Problem
• Two results on the digraph chromatic number
• Uniquely D-colourable digraphs with large girth
• χ‐bounded families of oriented graphs

Cited in

(18)

• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded
• Chordal directed graphs are not \(\chi\)-bounded
• Decomposing and colouring some locally semicomplete digraphs
• Dichromatic number and fractional chromatic number
• Extending the Gyárfás-Sumner conjecture
• Heroes in orientations of chordal graphs
• Complete directed minors and chromatic number
• On coloring digraphs with forbidden induced subgraphs
• Four proofs of the directed Brooks' theorem
• Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P₄
• Heroes in oriented complete multipartite graphs
• Bounding the chromatic number of dense digraphs by arc neighborhoods
• 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)
• Clique number of tournaments

This page was built for publication: Extension of Gyárfás-Sumner conjecture to digraphs

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