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:
- $G$ is a union of vertex-disjoint cycles: $\chi'= 3 = \Delta+1$
- $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.
Best Answer
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.