Draft:Directed Coloring
| Submission declined on 24 October 2023 by DoubleGrazing (talk). This submission is not adequately supported by reliable sources. Reliable sources are required so that information can be verified. If you need help with referencing, please see Referencing for beginners and Citing sources. This draft's references do not show that the subject qualifies for a Wikipedia article. In summary, the draft needs multiple published sources that are:
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
|  |
Comment: A single source, once cited, is neither enough to support the contents nor to establish notability per WP:GNG. DoubleGrazing (talk) 06:37, 24 October 2023 (UTC)
In graph theory, directed coloring (or dicoloring) is an analogue of graph coloring for directed graphs. A directed coloring is an assignment of colours to vertices of a directed graph so that no directed cycle is monochromatic. Alternatively, it can be defined as an assignment of colors to vertices in a manner that ensures the directed graph induced by any color is acyclic.
The dichromatic number (also known as the directed chromatic number) of a directed graph is the minimum number of colors required to achieve a valid directed coloring.
This definition was coined by Victor Neumann-Lara in 1982.[1]
Examples[edit]
A directed cycle has dichromatic number two, since it does not admit any directed coloring with only one color and any assignment that uses two colors is a directed coloring. A directed acyclic graph has dichromatic number one, since assigning the same color to every vertex yields a directed coloring with one color.
Properties[edit]
The dichromatic number of a directed graph is equal to the highest dichromatic number among its strongly connected components.
By replacing each edge of a graph by two opposite arcs, one obtain a directed graph whose dichromatic number is equal to the chromatic number of .
Since an independent set is acyclic, the dichromatic number of a directed graph is always greater than or equal to the chromatic number of its underlying graph. Note that the converse does not hold, since a transitive tournament on vertices has dichromatic number one, yet its underlying graph is a complete graph on vertices, which has chromatic number .
See also[edit]
- Oriented coloring, another way of defining coloring for directed graphs
References[edit]
- ^ Neumann-Lara, V. (1982), "The dichromatic number of a digraph", Journal of Combinatorial Theory, Series B, 33 (3): 265–270, doi:10.1016/0095-8956(82)90046-6.