Home » Subject » Graph Theory » Directed Graphs

The Two Color Conjecture

Importance: Medium ✭✭
Author(s): Neumann-Lara, Victor
Subject: Graph Theory
» Directed Graphs
Keywords: acyclic
digraph
planar
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.

Bibliography

* [N] V. Neumann-Lara (1985). Vertex colourings in digraphs. Some problems. Technical report, University of Waterloo.


* indicates original appearance(s) of problem.
add new comment

Riste Skrekovski conjectured

On May 31st, 2007 Anonymous says:

Riste Skrekovski conjectured at a graph theory meeting in Budmerice, Slovakia, in 2005 that this conjecture is false.

reply

Comment viewing options

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