# Chromatic index of a graph, all cycles of which are of odd length

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.

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

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.

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