Uniquely Colorable Graph

A uniquely -colorable graph is a finite simple graph with chromatic number such that every -coloring gives the same set partition of the vertices of (Cartwright and Harary 1968; Harary et al. 1969; Bollobás 1978; Harary 1994, pp. 137-140; Chao 2001; Brešar et al. 2023). Equivalently, a graph with chromatic number is uniquely colorable iff its vertices can be partitioned into independent vertex sets in exactly one way. It is important to note that this definition does not take the action of a graph automorphism group into account when considering uniqueness, so any symmetries in the graph itself are ignored (i.e., the vertices are considered "fixed").

Examples of uniquely colorable classes of graphs include complete graphs , connected bipartite graphs, complete multipartite graphs, and trees. k-trees are -uniquely colorable (Xu 1990).

The empty graphs (for ) are the only disconnected graphs that are uniquely colorable.

Chartrand and Geller (1969) proved that there are no uniquely 5-colorable planar graphs, and Fowler (1998, pp. 3-4) characterized uniquely 4-colorable planar graphs as exactly the planar 3-trees (cf. Brešar et al. 2023, who omit the "planar" restriction on 3-trees).

The numbers of simple uniquely colorable graphs on , 2, ... nodes are 1, 2, 3, 6, 11, 35, 134, 1183, 21319, ... (OEIS A369223).

Uniquely -colorable graphs are -connected (Chartrand and Geller 1969).

Uniquely -colorable graphs satisfy

(1)

where is the minimum vertex degree (Brešar et al. 2023).

Bollobás (1978) showed that a sufficient condition for a k-colorable graph on vertices and edges to be uniquely -colorable is that the inequality

(2)

hold. The condition is however not necessary, i.e., there exist graphs that are uniquely colorable but for which the inequality fails to hold.

Truszczyński (1984) and Xu (1990) gave a necessary condition for a graph with chromatic number , vertices, and edges to be uniquely colorable as satisfaction of the inequality

(3)

A graph is therefore not uniquely colorable if the inequality fails to hold, while a graph may or may not be uniquely colorable if it does hold.

Chao (2001, pp. 93-94) proved that there exist uniquely -colorable graphs with and vertices for every integer . For each such , he also proved the existence of a pair of uniquely -colorable graphs, each with vertices, that are chromatically equivalent, and a separate such pair, each with vertices.

Harary et al. (1969) and Harary (1994, cover and p. 139) gave two graphs that were incorrectly identified as uniquely colorable (as can be seen by the existence of distinct set partitions of vertices by color in the illustrations above). The first was corrected in Harary et al. (1970) through the addition of edges on the left, top, and right.

A different definition of unique colorability considers two colorings to be equivalent if there exists a composition of graph automorphism and color exchange that transforms one coloring into the other (Osterweil 1974, Chia 1996, Brešar et al. 2023). To distinguish this case from the more usual definition in which the action of the graph automorphism group has been dropped, Chia (1996) uses the term "uniquely colorable under the action of the graph automorphism group," while Brešar et al. (2023) term such graphs -iso-unique. Some graphs may be uniquely colorable under the action of their graph automorphism group based on the symmetry of the graph alone, i.e., the graph automorphism group itself acts to exchange colors in all possible ways without the need to take color exchange into account explicitly. Examples include the planar Sierpiński gasket graphs (D. Knuth, pers. comm., May 1, 2022).