Name
Abstract | ||
|---|---|---|
The dichromatic number ($)over-right-arrow chi(D) of a digraph D is the minimum number of colors needed to color the vertices of D such that each color class induces an acyclic subdigraph of D. A digraph D is k-critical if ($)over-right-arrow chi(D) = k but chi(D') < k for all proper subdigraphs D' of D. We examine methods for creating infinite families of critical digraphs, the Dirac join and the directed and bidirected Hajos join. We prove that a digraph D has dichromatic number at least k if and only if it contains a subdigraph that can be obtained from bidirected complete graphs on k vertices by directed Hajos joins and identifying non-adjacent vertices. Building upon that, we show that a digraph D has dichromatic number at least k if and only if it can be constructed from bidirected K-k's by using directed and bidirected Hajos joins and identifying non-adjacent vertices (so called Ore joins), thereby transferring a well-known result of Urquhart to digraphs. Finally, we prove a Gallai-type theorem that characterizes the structure of the low vertex subdigraph of a critical digraph, that is, the subdigraph, which is induced by the vertices that have in-degree k - 1 and out-degree k - 1 in D. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.37236/8942 | ELECTRONIC JOURNAL OF COMBINATORICS |
DocType | Volume | Issue |
Journal | 27 | 1 |
ISSN | Citations | PageRank |
1077-8926 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jørgen Bang-Jensen | 1 | 573 | 68.96 |
| Thomas Bellitto | 2 | 2 | 2.78 |
| thomas schweser | 3 | 0 | 2.37 |
| Michael Stiebitz | 4 | 207 | 30.08 |