= Chromatic index bounds
{title2=$\Delta(G)\leq\chi\prime(G)\leq\Delta(G)+1$}
For every finite <simple graph>, <Vizing's theorem> gives
$$
\Delta(G)\leq\chi\prime(G)\leq\Delta(G)+1.
$$
Here $\Delta(G)$ is the <maximum degree of a graph>, taken as zero when there are no <vertices>. A <bipartite graph> has the stronger equality $\chi\prime(G)=\Delta(G)$. The six-job <complete bipartite graph> above attains this lower bound, while the <triangle in a graph> attains the extra-colour alternative. The simple-<graph> restriction in the upper bound matters.<Graph Theory by Reinhard Diestel>[Colouring, author-hosted chapter preview, §5.3, p. 132: Proposition 5.3.1 and Theorem 5.3.2]{ref}
The <bipartite graph> equality still holds for finite loopless <multigraphs>, with parallel <edges> counted separately in each <vertex degree>. For instance, $r$ parallel jobs between two resources need exactly $r$ slots: every pair conflicts, and $\Delta=\chi\prime=r$. For a general finite loopless <multigraph>, however, the <simple graph> upper bound can fail. Put two parallel <edges> on each side of a <triangle in a graph>. All six <edges> pairwise share a <vertex>, so each needs its own colour; every <vertex> has <degree of a vertex> four. Consequently $\chi\prime=6>\Delta+1=5$. A multiplicity-aware bound is $\chi\prime(G)\leq\Delta(G)+\mu(G)$, where $\mu(G)$ is the largest number of parallel <edges> between a pair of <vertices>. The doubled <triangle in a graph> has $\mu=2$ and attains that bound. These statements exclude <self-loops>; the two-distinct-resource scheduling model excludes them too.<Line graphs and edge coloring>[Line graphs and edge coloring, slide 2: bipartite multigraph equality, multiplicity bound and fat triangle]{ref}
For historical orientation, <Graph Theory by Reinhard Diestel> (Colouring preview, §5.3, p. 132) dates the bipartite equality to 1916 and <Vizing's theorem> to 1964. These are textbook attributions; the original papers have not been inspected here. The results state existence of optimal or nearly optimal <proper edge colourings>, rather than saying that arbitrary greedy choices will find them. The <list-chromatic index> asks the further question of success for every sufficiently large family of allowed-colour lists.
Back to article page
