Consider a connected, planar, directed graph G whose vertices are either degree 1 or 3. Suppose further that at each order 3 vertex of G either (1) exactly two of the three adjacent edges are oriented inwards (i.e., towards the vertex) and the third edge points outwards (away from the vertex), or (2) two edges point outwards, one inwards. Assign to each order 3 vertex either 1 or 2 according to which case holds.

If such a labeling of the order 3 vertices exists such that 1s and 2s are never adjacent, this gives a 2-coloring of G (the order 1 vertices are colored canonically after the order 3s are). Is it true that if such a graph G as above is 2-colorable, then there is a 2-coloring arising in this way?


Not always. Here is a $3$-regular directed planar graph in which every vertex has $1$ or $2$ edges pointing in and $2$ or $1$ edges pointing out, and which is $2$-colorable; however, labeling vertices by outdegree doesn't produce a proper $2$-coloring.

cube orientation

(The outside cycle gets label $2$, and the inside cycle gets label $1$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.