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.


Comments are limited to a maximum of 1000 characters.
More information about formatting options