The Two Color Conjecture

Importance: Medium ✭✭
Keywords: acyclic
Recomm. for undergrads: no
Prize: none
Posted by: mdevos
on: March 26th, 2007
Conjecture   If $ G $ is an orientation of a simple planar graph, then there is a partition of $ V(G) $ into $ \{X_1,X_2\} $ so that the graph induced by $ X_i $ is acyclic for $ i=1,2 $.

This is a type of coloring digraphs introduced by V. Neumann-Lara. More generally, if $ G $ is a digraph, we wish to partition the vertex set of $ G $ into as few parts as possible so that each induces an acyclic subgraph.


* [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.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.