Chromatic index bounds 2026-10-14
For every finite simple graph, Vizing's theorem givesHere is the maximum degree of a graph, taken as zero when there are no vertices. A bipartite graph has the stronger equality . 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.[ref]
The bipartite graph equality still holds for finite loopless multigraphs, with parallel edges counted separately in each vertex degree. For instance, parallel jobs between two resources need exactly slots: every pair conflicts, and . 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 . A multiplicity-aware bound is , where is the largest number of parallel edges between a pair of vertices. The doubled triangle in a graph has and attains that bound. These statements exclude self-loops; the two-distinct-resource scheduling model excludes them too.[ref]
Line graphs and edge coloring. Line graphs and edge coloring, slide 2: bipartite multigraph equality, multiplicity bound and fat triangle
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.
Class two regular graph 2026-10-25
An -regular graph is class two when its edge chromatic number exceeds . For a finite simple graph, Vizing's theorem makes that edge chromatic number exactly . An -colour proper edge colouring of an -regular graph would partition its edges into perfect matchings, since every vertex would see each colour exactly once.
A proper edge colouring assigns colours to the edges of a graph so that distinct edges sharing a vertex have different colours. The edge chromatic number is the least number of colours in such an assignment. Equivalently, it is the least number of matchings in a graph whose disjoint union is the entire collection of edges.
Vizing's theorem states that a finite simple graph of maximum degree satisfiesThe lower bound holds because all edges incident with a vertex of vertex degree require different colours.
Hall's marriage theorem states that a finite bipartite graph with vertex sets has a matching in a graph saturating if and only ifwhere is the graph neighbourhood of . Here matching saturation means that each vertex of is incident with an edge of the matching in a graph; it does not require every vertex of to be met.
For even , take the complete graph . It is an -regular graph on an odd number of vertices. Every matching in a graph has at most edges, so colours in a proper edge colouring could cover at most edges. ButTherefore ; Vizing's theorem gives . This includes the graph triangle when .
For odd , first construct a graph on vertices. Start with the complete graph onand delete the edges , , and . The pairing is possible because is even. In the initial complete graph, every vertex has vertex degree . The distinguished vertex loses two edges and every other vertex loses exactly one, givingTake two disjoint copies of , with distinguished vertices , and add the edge . The resulting simple graph is an -regular graph. The added edge is the only edge between the two copies; each copy has the odd number of vertices.
Suppose an -colour proper edge colouring existed. At each vertex, the incident edges would use all colours. Thus each colour would form a perfect matching. Any perfect matching must use : without it, each odd-sized copy would have to be covered by internal pairs, which is impossible by parity. Therefore all colour classes would have to contain the same edge , a contradiction. Hence Vizing's theorem again givesThese constructions give class two regular graphs for every . The odd- construction exhibits the bridge obstruction to regular edge colouring; is a connected graph because every vertex other than is adjacent to , while are adjacent to those vertices.