
arXiv: 1510.03578
AbstractThe dichromatic number 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 article, 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 . We finally give a Brooks‐type upper bound on the list dichromatic number of digon‐free digraphs.
list coloring, dichromatic number, 500, Directed graphs (digraphs), tournaments, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], list dichromatic number, 510, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Coloring of graphs and hypergraphs, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), digraphs
list coloring, dichromatic number, 500, Directed graphs (digraphs), tournaments, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], list dichromatic number, 510, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Coloring of graphs and hypergraphs, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), digraphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 12 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
