![](/files/happy5.png)
The Two Color Conjecture
Conjecture If
is an orientation of a simple planar graph, then there is a partition of
into
so that the graph induced by
is acyclic for
.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ V(G) $](/files/tex/b324b54d8674fa66eb7e616b03c7a601ccdab6b8.png)
![$ \{X_1,X_2\} $](/files/tex/1ac50179d3c46ba43d2b8183a945de84c223f351.png)
![$ X_i $](/files/tex/4d0fffaf276df9eeca81fca1efb9e42157b0a9f9.png)
![$ i=1,2 $](/files/tex/1db9f0079a9ca23741381d2fbc830c48d730c458.png)
This is a type of coloring digraphs introduced by V. Neumann-Lara. More generally, if is a digraph, we wish to partition the vertex set of
into as few parts as possible so that each induces an acyclic subgraph.
Bibliography
* [N] V. Neumann-Lara (1985). Vertex colourings in digraphs. Some problems. Technical report, University of Waterloo.
* indicates original appearance(s) of problem.
Riste Skrekovski conjectured
Riste Skrekovski conjectured at a graph theory meeting in Budmerice, Slovakia, in 2005 that this conjecture is false.