List coloring digraphs

DOI10.1002/JGT.22170MaRDI QIDQ4638642zbMATH OpenOpenAlexFDO

Authors Julien Bensmail, Ararat Harutyunyan, Ngoc Khang Le

Publication date 27 April 2018

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

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

zbMATH Keywords

dichromatic numberdigraphslist coloringlist dichromatic number

Mathematics Subject Classification ID

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

Abstract: The dichromatic number $vecchi(D)$ of a digraph $D$ is the least number $k$ such that the vertex set of $D$ can be partitioned into $k$ parts each of which induces an acyclic subdigraph. Introduced by Neumann-Lara in 1982, this digraph invariant shares many properties with the usual chromatic number of graphs and can be seen as the natural analog of the graph chromatic number. In this paper, we study the list dichromatic number of digraphs, giving evidence that this notion generalizes the list chromatic number of graphs. We first prove that the list dichromatic number and the dichromatic number behave the same in many contexts, such as in small digraphs (by proving a directed version of Ohba's Conjecture), tournaments, and random digraphs. We then consider bipartite digraphs, and show that their list dichromatic number can be as large as $Omega(lo{g}_{2}n)$. We finally give a Brooks-type upper bound on the list dichromatic number of digon-free digraphs.

Recommendations

• List colourings of graphs
• List coloring hypergraphs
• Colouring non-even digraphs
• List-colourings
• List-colourings of graphs
• List-distinguishing colorings of graphs
• scientific article; zbMATH DE number 7637228
• List-coloring embedded graphs
• scientific article; zbMATH DE number 5531976
• Sum list coloring graphs

Cited in

(19)

• The diachromatic number of digraphs
• A note on coloring digraphs of large girth
• Extension of Gyárfás-Sumner conjecture to digraphs
• Majority colorings of sparse digraphs
• Dichromatic number and forced subdivisions
• Colouring non-even digraphs
• On the dichromatic number of surfaces
• The NL-flow polynomial
• Decomposing and colouring some locally semicomplete digraphs
• Dichromatic number and fractional chromatic number
• scientific article; zbMATH DE number 4150191 (Why is no real title available?)
• scientific article; zbMATH DE number 3918396 (Why is no real title available?)
• Four proofs of the directed Brooks' theorem
• Coloring \(k\)-partite sparse digraphs
• Digraph coloring and distance to acyclicity
• Colouring complete multipartite and Kneser-type digraphs
• Colouring complete multipartite and Kneser-type digraphs (extended abstract)
• Digraph coloring and distance to acyclicity
• Clique number of tournaments

This page was built for publication: List coloring digraphs

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