1 Definition and basic concepts

The chromatic index of a graph is the smallest number of colors needed to color its edges so that no two edges meeting at a common endpoint receive the same color. This parameter is the edge-coloring counterpart of the chromatic number, which concerns vertex colorings. It is commonly used to measure how efficiently the edges of a graph can be partitioned into disjoint color classes, each of which forms a matching.

1.1 Edge coloring

An edge coloring assigns a color to each edge of a graph. In a proper edge coloring, every color class is a set of pairwise nonadjacent edges. Equivalently, each color class is a matching, since no two edges of the same color are allowed to share an endpoint. Edge coloring is especially natural in problems where edges represent pairwise connections, tasks, or interactions that cannot occur simultaneously if they touch the same vertex.

1.2 Adjacent edges and proper colorings

Two edges are adjacent if they share a common endpoint. A proper edge coloring prohibits adjacent edges from sharing a color. This condition ensures that each vertex is incident to edges of distinct colors. As a result, if a graph has maximum degree \(\Delta\), then at least \(\Delta\) colors are needed, because the edges incident to a vertex of degree \(\Delta\) must all be differently colored.

1.3 Chromatic index notation

The chromatic index of a graph \(G\) is usually written as \(\chi'(G)\). If \(G\) is simple, \(\chi'(G)\) denotes the least number of colors in a proper edge coloring. For multigraphs, the same notation is used, but multiple edges may alter the minimum number of colors required. The prime in the notation distinguishes edge coloring from the chromatic number \(\chi(G)\) of vertex coloring.

1.4 Examples of edge colorings

A path graph can often be edge-colored with two colors by alternating colors along the path. A triangle requires three colors, since each edge touches the other two. A square, however, can be colored with two colors by alternating colors around the cycle. These examples show that the chromatic index can vary significantly even among small and structurally similar graphs.

2 Fundamental properties

The chromatic index is controlled by a graph’s local structure, especially its maximum degree and the arrangement of adjacent edges. Many of its basic properties follow from simple counting arguments, while deeper results depend on structural theorems about edge decompositions.

2.1 Relation to maximum degree

The maximum degree \(\Delta(G)\) gives the most basic lower bound on the chromatic index. Since all edges meeting at a highest-degree vertex must have different colors, at least \(\Delta(G)\) colors are necessary. A central question in edge coloring is whether \(\Delta(G)\) colors always suffice or whether one more color is sometimes needed.

2.1.1 Lower bound by maximum degree

If a graph contains a vertex of degree \(\Delta\), then the \(\Delta\) incident edges must all receive distinct colors. Therefore \(\chi'(G) \ge \Delta(G)\). This bound is immediate and often sharp for many graph families, including all bipartite graphs by König’s line coloring theorem.

2.1.2 Upper bound by Vizing’s theorem

For every simple graph, Vizing’s theorem states that the chromatic index is either \(\Delta\) or \(\Delta+1\). This result is one of the cornerstone theorems of edge coloring. It shows that simple graphs fall into only two possible regimes, which leads to the classification into Class 1 and Class 2 graphs.

2.2 Multigraphs and simple graphs

In multigraphs, multiple edges between the same pair of vertices can force a larger chromatic index than in a corresponding simple graph. The behavior of multigraph edge coloring is more delicate, and the gap between lower and upper bounds can be wider. Classical theorems for multigraphs include Shannon’s theorem, which provides a general upper bound in terms of maximum degree.

2.3 Connection to line graphs

Edge coloring of a graph \(G\) is equivalent to vertex coloring of its line graph \(L(G)\). In the line graph, each edge of \(G\) becomes a vertex, and two such vertices are adjacent when the original edges share an endpoint. Under this correspondence, a proper edge coloring of \(G\) becomes a proper vertex coloring of \(L(G)\). This equivalence allows results from vertex coloring to be transferred into the edge-coloring setting.

3 Exact values for common graph families

For many standard families of graphs, the chromatic index can be determined exactly. These formulas often reveal the influence of parity, regularity, and bipartite structure on edge-coloring behavior.

3.1 Complete graphs

For a complete graph \(K_n\), the chromatic index depends on whether \(n\) is even or odd. If \(n\) is even, then \(\chi'(K_n)=n-1\). If \(n\) is odd, then \(\chi'(K_n)=n\). This difference reflects the fact that a 1-factorization exists only when the number of vertices is even. In the odd case, one additional color is needed beyond the maximum degree.

3.2 Complete bipartite graphs

Complete bipartite graphs \(K_{m,n}\) have chromatic index equal to their maximum degree, namely \(\max(m,n)\). This follows from the bipartite structure, which permits an edge decomposition into matchings of optimal size. The result is a key example of a family where the lower bound from maximum degree is always attained.

3.2.1 König’s line coloring theorem

König’s line coloring theorem states that every bipartite multigraph has edge chromatic number equal to its maximum degree. For simple bipartite graphs, this implies \(\chi'(G)=\Delta(G)\). The theorem is fundamental because it gives a complete and elegant answer for a broad class of graphs, and it underlies many applications in scheduling and allocation problems.

3.3 Cycles

The chromatic index of a cycle depends on the parity of its length. An even cycle can be edge-colored with two colors by alternating colors around the cycle. An odd cycle requires three colors, because alternating colors cannot close consistently when the number of edges is odd. Thus, even cycles are Class 1 and odd cycles are Class 2.

3.4 Paths and trees

Any path with at least one edge has chromatic index 2, except for the single-edge graph, which has chromatic index 1. More generally, every tree has chromatic index equal to its maximum degree. Since trees are bipartite, this is a direct consequence of König’s theorem. The edge coloring of trees is often easy to construct recursively by coloring pendant edges and extending inward.

3.5 Regular graphs

For regular graphs, the chromatic index is closely tied to parity and structural constraints. A regular graph of even degree may often admit a decomposition into perfect matchings, leading to chromatic index equal to the degree. In other cases, especially among odd-regular simple graphs, the chromatic index may be one more than the degree. Regular graphs therefore provide many important examples of both Class 1 and Class 2 behavior.

4 Classification by chromatic index

Graphs are commonly classified according to whether their chromatic index equals the maximum degree or exceeds it by one. This classification is particularly useful for simple graphs, where Vizing’s theorem limits the possibilities.

4.1 Class 1 graphs

A graph is Class 1 if its chromatic index equals its maximum degree. Many graphs belong to this class, including all bipartite graphs, all trees, and numerous regular graphs. Class 1 graphs are often those for which the edges can be partitioned into the smallest possible number of matchings.

4.2 Class 2 graphs

A graph is Class 2 if its chromatic index is \(\Delta+1\). Such graphs require one more color than the maximum degree lower bound. Complete graphs of odd order and odd cycles are familiar examples. Identifying Class 2 graphs is generally more difficult than identifying Class 1 graphs, and the structure of Class 2 graphs is a major topic in edge-coloring theory.

4.3 Deciding the class of a graph

Determining whether a given simple graph is Class 1 or Class 2 can be computationally challenging. For general graphs, no simple characterization is known. The problem becomes more manageable for restricted families, such as bipartite graphs, planar graphs under certain conditions, or graphs with bounded degree. In practice, partial structure, symmetry, and decomposition methods are often used to infer the class.

5 Theorems and results

Several classical theorems form the core of chromatic index theory. They provide exact values in special cases and bounds in more general settings, linking edge coloring with matchings and graph decomposition.

5.1 Vizing’s theorem

Vizing’s theorem states that every simple graph has chromatic index either \(\Delta\) or \(\Delta+1\). It is a foundational result in graph theory and gives the basic dichotomy between Class 1 and Class 2 graphs. The theorem inspired extensive research into sufficient conditions for each case and into algorithms for finding edge colorings close to optimal.

5.2 König’s line coloring theorem

König’s line coloring theorem asserts that every bipartite multigraph has chromatic index equal to its maximum degree. This theorem is stronger than Vizing’s theorem for bipartite graphs, since it achieves the lower bound exactly. It is often proved using matchings and augmenting path arguments, and it has major applications in combinatorial optimization.

5.3 Shannon’s theorem for multigraphs

Shannon’s theorem gives an upper bound on the chromatic index of a multigraph in terms of its maximum degree \(\Delta\), namely \(\chi'(G) \le \frac{3}{2}\Delta\). This bound is especially relevant for graphs with multiple edges, where the simple-graph bound from Vizing’s theorem does not apply. Shannon’s theorem is an important early result in the study of edge colorings of multigraphs.

5.4 Decomposition into matchings

A proper edge coloring partitions the edge set into color classes, each of which is a matching. Thus, edge coloring can be viewed as decomposing a graph into as few matchings as possible. This perspective is useful in proofs, algorithm design, and applications, because it turns a coloring problem into a structural decomposition problem.

6 Algorithms and computational complexity

Computing or approximating the chromatic index is a significant algorithmic problem. Some graph classes admit efficient exact algorithms, while the general problem is computationally difficult.

6.1 Edge-coloring algorithms

For bipartite graphs, edge coloring can be solved efficiently using matching algorithms and constructive proofs of König’s theorem. For general simple graphs, there are polynomial-time algorithms that find edge colorings using at most \(\Delta+1\) colors, consistent with Vizing’s theorem. These methods often rely on recoloring techniques, augmenting structures, and careful local adjustments.

6.2 Complexity of determining the chromatic index

Determining whether a given graph is Class 1 or Class 2 is computationally hard in general. The exact chromatic index problem is especially challenging because the answer may hinge on subtle global structure. While efficient algorithms exist for important special cases, the general decision problem remains difficult and is studied in computational complexity and algorithmic graph theory.

6.3 Approximation and heuristic methods

Because exact edge coloring can be hard, approximation algorithms and heuristics are frequently used. Greedy coloring methods, local improvement strategies, and randomized procedures can produce good colorings quickly, though not always optimal ones. In practical settings, especially when graphs are large or dynamic, near-optimal edge colorings may be sufficient.

The chromatic index is part of a broader network of coloring notions in graph theory. It connects naturally to other invariants and refinements that describe how edges and vertices interact under coloring constraints.

7.1 Chromatic number

The chromatic number \(\chi(G)\) is the minimum number of colors needed to color the vertices of a graph so that adjacent vertices differ in color. Like the chromatic index, it measures a form of nonadjacent partitioning, but it applies to vertices instead of edges. Comparing \(\chi(G)\) and \(\chi'(G)\) often highlights the difference between vertex-based and edge-based constraints.

7.2 Line graph coloring

Since edge coloring of \(G\) is equivalent to vertex coloring of its line graph \(L(G)\), many edge-coloring questions become vertex-coloring questions on a transformed graph. This correspondence is conceptually important and often simplifies proofs or reveals structural parallels. It also helps explain why edge-coloring results can be framed using familiar vertex-coloring language.

7.3 Edge chromatic polynomial

The edge chromatic polynomial counts the number of proper edge colorings of a graph using a given number of colors. It is the edge-coloring analogue of the chromatic polynomial for vertex colorings. Studying this polynomial provides information not only about the chromatic index but also about how the number of valid colorings grows as more colors are allowed.

7.4 Strong edge coloring

In a strong edge coloring, any two edges at distance at most one in the line graph must receive different colors. This is a stricter condition than ordinary proper edge coloring. The strong chromatic index, which measures the minimum number of colors needed, is therefore at least the chromatic index and is generally harder to determine.

8 Applications

Edge coloring is useful in situations where connections must be assigned to time slots, channels, or other resources without conflicts. Its combinatorial structure makes it a natural tool in scheduling and allocation problems.

8.1 Scheduling problems

In scheduling, edges may represent tasks requiring two resources, and adjacent edges represent tasks that share a resource. A proper edge coloring then assigns tasks to time slots so that no resource is used twice at the same time. This viewpoint is common in job scheduling, transportation planning, and tournament design.

8.2 Frequency assignment

In communication networks, edges may represent links that must use different frequencies when they interfere with one another at a shared endpoint. Edge coloring provides a model for assigning frequencies while avoiding local conflicts. The chromatic index gives a theoretical lower limit on the number of frequencies needed.

8.3 Timetabling and resource allocation

Edge-coloring models also arise in timetabling and resource allocation, where pairwise interactions must be separated into conflict-free groups. For example, a set of pairings or meetings can be arranged so that no participant appears in two simultaneous events. In such settings, color classes correspond to parallelizable rounds or schedules.

9 Historical development

The study of edge coloring developed alongside broader work in graph coloring and combinatorics. Over time, it became a distinct area with its own central theorems, methods, and applications.

9.1 Early results in graph coloring

Early graph-theoretic work focused mainly on vertex coloring, but edge-coloring questions soon emerged as natural analogues. Classical combinatorial arguments and matching theory provided some of the first systematic tools for understanding edge partitions. These foundations helped connect coloring problems with factorization and decompositions.

9.2 Contributions by Vizing and König

König established the line coloring theorem for bipartite graphs, giving an exact answer for a major family of graphs. Later, Vizing proved his theorem for simple graphs, showing that the chromatic index is always either \(\Delta\) or \(\Delta+1\). Together, these results created the modern framework for edge coloring and remain among the most influential theorems in the subject.