Chromatic index $\chi'$ of a graph is the minimum number of colors in an edge coloring where each edge is assigned a color such that no two adjacent edges have the same color; $\Delta(G)=\max_{v\in V(G)}(d(v))$ - highest degree of a vertex in $G$.

Let $G$ be a simple undirected graph, and let each simple (non-self-intersecting) cycle $C\in G$ be of odd length. What is the chromatic index $\chi'$ of $G$?

I have found some trivial cases:

  1. $G$ is a union of vertex-disjoint cycles: $\chi'= 3 = \Delta+1$
  2. $G$ does not contain any cycles: $\chi' = \Delta$

Brute force seems to suggest for any case other than 1. $\chi' = \Delta$, but I'm struggling to prove this.

  • $\begingroup$ Are you aware of Vizing’s theorem and trying for a complete classification in the special case of graphs with no even simple cycles? $\endgroup$ Oct 4, 2020 at 0:19
  • $\begingroup$ @BrianM.Scott Yes, I am aware of it, and yes, that is what I'm trying to accomplish. $\endgroup$
    – lsparki
    Oct 4, 2020 at 10:30

1 Answer 1


You are right, if $\Delta(G)>2$ and all cycles of $G$ are odd then $\chi'(G)=\Delta(G)$.

You can prove this by induction on the number of cycles in $G$. We my assume $G$ is connected, since if it is true for every connected graph we can just colour components separately.

If $G$ has no cycles then it is a tree. Root it at any vertex, and colour edges one by one in order of distance from the root. We can do this using a greedy algorithm with $\Delta$ colours: when we colour an edge, the only incident edges we have previously coloured all meet it at the same endpoint, so there are at most $\Delta-1$ forbidden colours.

If there is exactly one cycle, then we can do the same thing. First, colour the cycle with $3\leq \Delta$ colours. Now colour the other edges in order of distance from the cycle; the same argument works.

If there are two or more cycles, choose two and call them $C_1,C_2$. If they have a vertex $v$ in common, note that there can be no path between the cycles that does not go through $v$, since if there is such a path $P$ we could construct a cycle by going along $P$, round $C_2$ to $v$, and round $C_1$ to the start of $P$. Since both cycles are odd, and we can choose which direction to go round them, we can make this new cycle of either parity, a contradiction. Thus $v$ is a cutvertex, and we can find two graphs $G_1,G_2$, with no common edges and no common vertices other than $v$, such that $G$ is obtained by gluing $G_1$ and $G_2$ together at $v$, and each containing one of the cycles. By induction, we can define two colourings $c_1,c_2$ of $G_1,G_2$ respectively, each with colours from $\{1,...,\Delta(G)\}$. Since $\Delta(G)\geq d_G(v)$ we can reorder the colours for $c_2$, if necessary, so that the set of colours used at $v$ by $c_2$ is disjoint from those used at $v$ by $c_1$.

If $C_1,C_2$ do not have a vertex in common, then by a similar argument there cannot be two vertex-disjoint paths between them (otherwise there would be cycles of either parity using these paths and part of $C_1,C_2$). This means, via Menger's theorem, that there is a single vertex $v$ such that all paths between them go through $v$, and now you can do the same thing.

  • $\begingroup$ I guess the cycle can be coloured with $3\le\Delta+1$ colours. $\endgroup$ Oct 5, 2020 at 12:16
  • 1
    $\begingroup$ @AlexRavsky under the assumption $\Delta>2$ (given at the top of the answer) $3\le \Delta$ is correct $\endgroup$
    – lsparki
    Oct 5, 2020 at 12:21

You must log in to answer this question.

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