7
$\begingroup$

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.)

Improve this question
$\endgroup$
4
  • $\begingroup$ What if the the head of one edge is the tail of another, could they have the same color? $\endgroup$
    – w g
    Commented May 11, 2012 at 0:47
  • $\begingroup$ Do you assume that for every edge there are two directed edges, $uv$ and $vu$? $\endgroup$
    – Gjergji Zaimi
    Commented May 12, 2012 at 6:32
  • $\begingroup$ 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. $\endgroup$
    – w g
    Commented May 12, 2012 at 8:42
  • $\begingroup$ Gjergji - yes. w.g.'s first comment - they can have the same color; w.g. second comment, I dont see it. $\endgroup$
    – Gil Kalai
    Commented May 12, 2012 at 13:27

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Flo Pfender
    Commented May 15, 2012 at 12:34
  • $\begingroup$ 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. $\endgroup$
    – Gjergji Zaimi
    Commented May 15, 2012 at 12:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .