Home » Subject » Graph Theory » Directed Graphs
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.
1 comment

Reply

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