MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let G be a graph and let C be a set of coloring. Suppose that there is an involution $\phi$ from C to C. We can think about the element of C as the nonzero elements of some Abelian group and $\phi(x)=-x$. (For concreteness we can consider especially the special case that C corresponds to the cyclic group, so that $\phi$ has no fixed points when |C| is even and one fixed point when |C| is odd.)

Consider a colorings where for every edge {u,v} in G we color the directed edge from u to v with some color c and the directed edge from v to u with -c. We will also require that two edges with the same tail and two edges with the same head must have different colors. If $\phi$ is the identity this is a usual edge coloring of $G$.

My question is if such colorings were considered and what is known about them. For example, is there an analog of Vizing theorem? (Vizing theorem asserts that the edges of every graph with maximum degree d can be colored by d+1 colors.)

share|cite|improve this question
What if the the head of one edge is the tail of another, could they have the same color? – w g May 11 '12 at 0:47
Do you assume that for every edge there are two directed edges, $uv$ and $vu$? – Gjergji Zaimi May 12 '12 at 6:32
If that was the case then the problem becomes a regular edges coloring. Just color the undirected version of G using the pairs {x, -x} as colors. – w g May 12 '12 at 8:42
Gjergji - yes. w.g.'s first comment - they can have the same color; w.g. second comment, I dont see it. – Gil Kalai May 12 '12 at 13:27

It seems to me that such colorings are closely related to 2-factorizations of graphs. Indeed every color class represents a subgraph which is a disjoint union of directed paths and cycles. Let's denote by $C(x)$ the set of edges colored $x\in G$. We can see that the underlying graphs of $C(x)$ and $C(-x)$ coincide, but they have opposite orientation. When $2x\neq 0$ then the underlying subgraph must have maximum degree 2. When $2x=0$ then $C(x)$ is a matching.

It's possible to show that a graph with $n$ vertices and maximum degree $\Delta$ can be written as a union of at most $\lfloor \frac{\Delta+1}{2}\rfloor$ subgraphs of maximum degree 2. Each of these subgraphs is a union of paths and cycles, so we can assign two colors to the corresponding directed edges. This shows that there is always a coloring satisfying the properties in the question coming from $\mathbb Z/(\Delta+1)\mathbb Z$. This would be the most straightforward analog of Vizing's theorem. Notice that $\Delta+1$ cannot be improved.

share|cite|improve this answer
You get the significant part of the "it's possible" part directly from Vizing's Theorem, by joining two color classes. Not quite ⌊(Δ+1)/2⌋, but the conclusion holds. – Flo Pfender May 15 '12 at 12:34
Right, because you can pair up color classes from Vizing's theorem and if you're left with an extra matching assign it the value $0$ from our abelian group. – Gjergji Zaimi May 15 '12 at 12:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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