5
$\begingroup$

Let $G=(V, E)$ be an acyclic digraph (DAG) with all in- and out-degrees at most $k$. Is it true that the edges of $G$ may be always colored properly in $2k$ colors?

In the discussion of this question it is proved (for $k=2$, but the proofs work verbatim for other values of $k$) that $G$ has $|E|/(2k)$ disjoint edges.

Improve this question
$\endgroup$
12
  • $\begingroup$ Isn't this just asking for the acyclic chromatic index of graphs with maximum degree $2k$? $\endgroup$
    – vidyarthi
    Commented Mar 7, 2023 at 10:34
  • $\begingroup$ @vidyarthi what is acyclic chromatic index? $\endgroup$
    – Fedor Petrov
    Commented Mar 7, 2023 at 12:20
  • $\begingroup$ By Vizing's theorem, any counterexample would have to have a vertex with both in-degree $k$ and out-degree $k$, and the underlying undirected graph would have to be a class two graph. The usual suspects for class two graphs don't work here, but of course that doesn't prove much. $\endgroup$
    – Timothy Chow
    Commented Mar 7, 2023 at 13:27
  • 1
    $\begingroup$ Did you try Galvin's approach for the more general list coloring problem, as described by Zeilberger at: arxiv.org/abs/math/9506215 ? $\endgroup$
    – Abdelmalek Abdesselam
    Commented Mar 7, 2023 at 14:44
  • 1
    $\begingroup$ I still suspect that Vizing's theorem is a more promising direction. If you haven't consulted it already, I'd recommend looking at the book Graph Edge Coloring by Stiebitz et al. Your result may not be in there, but I think there's a good chance that the techniques of that book will apply. $\endgroup$
    – Timothy Chow
    Commented Mar 7, 2023 at 16:49

2 Answers 2

Reset to default
3
$\begingroup$

Here is a solution (obtained while discussing the question with my colleague András Sebő).

Consider the undirected graph $H$ obtained from $G$ as follows: the partite sets of $H$ are two copies $V_1$ and $V_2$ of $V(G)$, and for each arc $(u,v)$ in $G$ we add an edge in $H$ between the copy of $u$ in $V_1$ and the copy of $v$ in $V_2$.

The graph $H$ is bipartite and has maximum degree $k$. By Kőnig's theorem $H$ has a proper $k$-edge-coloring, that is a partition of its edges into $k$ matchings $M_1,\ldots,M_k$. The edges of $H$ are in bijection with the arcs of $G$, and if we consider the image of each matching $M_i$ in $G$ we obtain a subgraph of $G$ with in-degree and out-degree at most 1 (that is, a disjoint union of directed cycles and directed paths). As $G$ is acyclic, the image of each matching $M_i$ in $G$ is a union of paths, so the edges of $G$ can be partitioned into $k$ subgraphs, each being a union of paths. As a union of paths is 2-edge-colorable, $G$ has a partition of its edges into $k$ 2-edge-colorable subgraphs, and is therefore $2k$-edge-colorable, as desired.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Oh, I completely missed this clever answer. $\endgroup$
    – Fedor Petrov
    Commented Apr 9, 2023 at 7:46
2
$\begingroup$

Of course, by "union of paths" we mean "vertex-disjoint union of paths". And we also got from the proof that "acyclic" can be replaced by the weaker condition "without odd directed cycle", i.e. :

A digraph with all in- and out-degrees at most k, and without directed cycle of odd size, has a 2k-edge-coloring.

Proof : From the associated bipartite graph above we get a partition of the edges into graphs each of which is a disjoint union of paths and even cycles, therefore each of them can in turn be partitioned into two matchings, yielding a partition of the original graph into 2k matchings. Q.E.D.

The bound is of course best possible as two vertices and k edges in both direction show.

Improve this answer
$\endgroup$

You must log in to answer this question.

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