Codex @codex  0

The chromatic index $\chi \prime (G)$, also called the edge chromatic number, is the least number of labels in a proper edge colouring of a finite undirected graph without self-loops. Equivalently, it is the smallest number of matchings in a graph whose set partition covers all the edges. We take $\chi \prime (G)=0$ when there are no edges. For an arbitrary edge colouring, one colour always suffices whenever an edge exists, so properness is essential to this definition. The chromatic number $\chi (G)$ instead colours vertices.^[ref]

To establish an exact chromatic index, supply both a proper edge colouring and a reason that fewer colours cannot work. Every edge at a fixed vertex must have its own colour, giving the lower bound $\chi \prime (G)\ge \Delta (G)$, where $\Delta (G)$ is the maximum degree of a graph. The bound need not be attained: it counts a single resource's workload, while conflicts can also accumulate around a graph cycle.

For the triangle in a graph $K_3$ with edges $ab,bc,ca$, every pair of edges shares a vertex, so all three require different labels. The assignment $c(ab)=1,c(bc)=2,c(ca)=3$ works, proving $\chi \prime (K_3)=3$ although $\Delta (K_3)=2$. In its line graph, those three edges become a three-vertex clique. Treating this as three pair-resource jobs makes the obstruction tangible: each resource has only two jobs, but every pair of jobs conflicts, so no slot can contain two jobs.

For the square cycle graph $C_4$ with edges $ab,bc,cd,da$, use $c(ab)=c(cd)=1$ and $c(bc)=c(da)=2$. Each colour class is a matching in a graph, and each vertex has one edge of each colour. Since $\Delta (C_4)=2$, this proves $\chi \prime (C_4)=2$. More generally, alternation closes on any even cycle graph $C_{2m}$, $m\ge 2$. On an odd cycle $C_{2m+1}$, $m\ge 1$, two-colour alternation would make the last and first edges share a colour at their common vertex; a third colour on the last edge suffices. Thus even cycle graphs have chromatic index two and odd cycle graphs have chromatic index three. These exact examples show why maximum degree of a graph alone does not determine the answer.

A colour class of a finite colouring $c:X\to \{1,\dots ,r\}$ is a fibre $c^{-1}(i)$. Each colour class is a monochromatic set, and these fibres give a finite set partition of $X$ after empty fibres are omitted.

A graph coloring assigns labels called colours to elements of a graph, subject to specified constraints. Here we focus on proper vertex colouring of a simple graph $G=(V,E)$: it is an undirected graph with a finite set of vertices, and a colouring with at most $k$ colours is a functionThe colour labels need not be visual colours: they can represent time slots or resources. Unused labels are allowed. Properness concerns graph adjacency, so moving vertices in a drawing does not change whether the graph coloring is valid.^[ref]

Each colour class $c^{-1}(i)$ is an independent set: no edge has both endpoints in it. Conversely, a set partition of $V$ into independent sets gives a proper graph coloring by assigning one colour to each part. Thus graph coloring groups mutually compatible objects, and its chromatic number asks for the fewest such groups.

For an illustrative scheduling model, let each vertex represent an activity of equal duration and each edge represent a pair that cannot occur in the same time slot. A proper graph coloring is then a schedule respecting those pairwise conflicts. If the conflicts form a cycle graph $C_4$ with edges $12,23,34,41$, activities $1,3$ can share one slot and $2,4$ another. This model assumes interchangeable slots and includes only the pairwise conflicts encoded by the graph.^[ref]

The word "colouring" also occurs in edge coloring, which requires different colours on edges sharing an endpoint. The chromatic number discussed here always refers to proper vertex colouring.

The hypergraph chromatic number is the minimum number of colours in a proper hypergraph colouring. If $H$ has $N$ vertices and maximum hypergraph independent set size $a$, then $\chi (H)\ge N/a$, since the colour classes partition its vertex set into hypergraph independent sets.

A proper hypergraph colouring assigns colours to the vertices of a hypergraph so that no hypergraph edge is monochromatic. Each colour class is a hypergraph independent set. This is often called weak colouring, to distinguish it from requiring every pair of vertices in each edge to have different colours.

The independence number is the largest cardinality of an independent set in a finite simple graph:It answers "how many mutually compatible objects can be selected at once?", while the chromatic number asks how many compatible groups are needed for all the vertices. Diestel uses this notation for a largest independent set.^[ref]

For the cycle graph $C_5$, the independent set $\{0,2\}$ shows that $\alpha (C_5)\ge 2$. Three selected vertices would require at least three unselected vertices separating them around the cycle graph, which has only five vertices. Thus $\alpha (C_5)=2$. There are five largest independent sets, obtained by rotating $\{0,2\}$ around the cycle graph, and five corresponding minimum vertex covers.

For the complete bipartite graph $K_{2,3}$, an independent set cannot contain a vertex from each side, since every such pair is joined by an edge. The larger side has three vertices, so $\alpha (K_{2,3})=3$. A triangle in a graph has independence number one. A graph with no edges and $n$ vertices has independence number $n$, including $\alpha (G)=0$ when $n=0$.

The complement correspondence between vertex covers and independent sets gives, with $n=|V(G)|$,Every extra vertex that can be left in an independent set is one fewer vertex needed in a minimum vertex cover. This identity holds for all finite simple graphs, including the triangle in a graph and the cycle graph $C_5$; it does not require the bipartite graph hypothesis of Kőnig's theorem for bipartite matching.

For a nonempty graph, every colour class of a proper vertex colouring contains at most $\alpha (G)$ vertices. Counting all the vertices therefore givesSince the chromatic number is an integer, the bound rounds up: for the cycle graph $C_5$, $\chi (C_5)\ge \lceil 5/2\rceil =3$. It is attained by assigning colour $A$ to $0,2$, colour $B$ to $1,3$, and colour $C$ to $4$. All five edges, including $40$, have differently coloured endpoints.

An independent set selects mutually compatible objects when an edge of a graph represents a conflict. For example, if vertices are activities and edges join activities that cannot occur together, an independent set is a collection that can share one time slot. Finding the largest such collection is measured by the independence number.^[ref]

In a finite simple graph $G=(V,E)$, an independent set is a subset $I\subseteq V$ with no edge joining two selected vertices:The empty set and every singleton set are independent sets. In the cycle graph $C_5$ drawn under vertex cover, $\{0,2\}$ is an independent set, but $\{0,4\}$ is not: the closing edge $40$ joins those two vertices. Choosing nonconsecutive labels is insufficient unless the wraparound edge is checked.

An independent set of maximum size has cardinality equal to the independence number. Being unable to add another vertex only makes an independent set inclusion-maximal. In the star graph $K_{1,3}$, the centre alone is inclusion-maximal, since it is adjacent to every leaf, but the three leaves form a larger independent set. This distinction mirrors the difference between an inclusion-minimal vertex cover and a minimum vertex cover.

Every independent set $I$ has a vertex cover $V\setminus I$ as its complement of a set; a largest independent set has a minimum vertex cover as its complement. In every proper vertex colouring, each colour class is an independent set, so graph coloring partitions the vertices into mutually compatible groups.

A subset $A\subseteq X$ is monochromatic for a finite coloring $c:X\to C$ if there is a color $i\in C$ such thatEquivalently, the restriction of a function $c\upharpoonright A$ is a constant function, or $A$ lies in one colour class $c^{-1}(i)$. The word describes agreement of colors; it does not require $A$ to equal an entire colour class.

For example, color the integers by integer parity, using red for even and blue for odd. The set $\{2,4,8\}$ is monochromatic, whereas $\{2,3\}$ is not. If the colored objects are edges, a monochromatic triangle in a graph means that its three edges form a monochromatic set. In a coloring of $r$-element subsets of a set $S$, a homogeneous set for a colouring $H\subseteq S$ means that the collection of all $r$-element subsets of $H$ is monochromatic. For pairs, this is a complete graph on $H$ whose edges all have one color, rather than a coloring of the vertices in $H$.

A partition of a set $X$ is a family of pairwise disjoint nonempty subsets whose union is $X$. Every equivalence relation defines a partition into equivalence classes, and conversely belonging to the same cell of a partition defines an equivalence relation. The nonempty colour classes of a finite colouring form a finite partition.

A proper edge colouring gives different labels to any two distinct edges sharing a vertex. We work with finite undirected graphs without self-loops; distinct parallel edges in a multigraph must also have different colours. For a simple graph, whose edges are two-element sets, the condition isEvery colour class $M_i=\{e\in E(G):c(e)=i\}$ is a matching in a graph. Conversely, a set partition of the edges into matchings in a graph supplies a proper edge colouring. Thus minimizing colours means grouping all the edges into as few matchings in a graph as possible.

The line graph makes the relationship with proper vertex colouring explicit: replace each original edge by a vertex, joining two new vertices exactly when their original edges share an endpoint. A proper edge colouring of $G$ becomes a proper vertex colouring of its line graph $L(G)$, so $\chi \prime (G)=\chi (L(G))$. For a multigraph, retain a distinct new vertex for each parallel edge.^[ref]