graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a uniquely colorable graph is a -chromatic

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

that has only one possible (proper) - coloring up to

permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...

of the colors. Equivalently, there is only one way to partition its vertices into independent sets and there is no way to partition them into independent sets.

Examples

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...

is uniquely colorable, because the only proper coloring is one that assigns each vertex a different color. Every ''k''-tree is uniquely (''k'' + 1)-colorable. The uniquely 4-colorable

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

s are known to be exactly the

Apollonian network In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maxim ...

s, that is, the planar 3-trees. Every connected

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

is uniquely 2-colorable. Its 2-coloring can be obtained by choosing a starting vertex arbitrarily, coloring the vertices at even distance from the starting vertex with one color, and coloring the vertices at odd distance from the starting vertex with the other color.

Properties

Some properties of a uniquely ''k''-colorable graph ''G'' with ''n'' vertices and ''m'' edges: # ''m'' ≥ (''k'' - 1) ''n'' - ''k''(''k''-1)/2.

Related concepts

Minimal imperfection

A ''minimal imperfect graph'' is a graph in which every subgraph is

perfect Perfect commonly refers to: * Perfection, completeness, excellence * Perfect (grammar), a grammatical category in some languages Perfect may also refer to: Film * Perfect (1985 film), ''Perfect'' (1985 film), a romantic drama * Perfect (2018 f ...

. The deletion of any vertex from a minimal imperfect graph leaves a uniquely colorable subgraph.

Unique edge colorability

A uniquely edge-colorable graph is a ''k''-edge-chromatic graph that has only one possible (proper) ''k''-edge-coloring up to permutation of the colors. The only uniquely 2-edge-colorable graphs are the paths and the cycles. For any ''k'', the

stars A star is an astronomical object comprising a luminous spheroid of plasma (physics), plasma held together by its gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked ...

''K''_1,''k'' are uniquely ''k''-edge-colorable. Moreover, conjectured and proved that, when ''k'' ≥ 4, they are also the only members in this family. However, there exist uniquely 3-edge-colorable graphs that do not fit into this classification, such as the graph of the

triangular pyramid In geometry, a tetrahedron (plural: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all the ...

. If a

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipa ...

is uniquely 3-edge-colorable, it must have exactly three

Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

s, formed by the edges with two of its three colors, but some cubic graphs with only three Hamiltonian cycles are not uniquely 3-edge-colorable. Every simple

planar Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...

cubic graph that is uniquely 3-edge-colorable contains a triangle, but observed that the

generalized Petersen graph In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways o ...

''G''(9,2) is non-planar, triangle-free, and uniquely 3-edge-colorable. For many years it was the only known such graph, and it had been conjectured to be the only such graph; . but now infinitely many triangle-free non-planar cubic uniquely 3-edge-colorable graphs are known.

Unique total colorability

A uniquely total colorable graph is a ''k''-total-chromatic graph that has only one possible (proper) ''k''-total-coloring up to permutation of the colors.

Empty graph In the mathematical field of graph theory, the term "null graph" may refer either to the order- zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph"). Order-zero graph The order-zero graph, , is ...

s, paths, and cycles of length divisible by 3 are uniquely total colorable graphs. conjectured that they are also the only members in this family. Some properties of a uniquely ''k''-total-colorable graph ''G'' with ''n'' vertices: # χ″(''G'') = Δ(''G'') + 1 unless ''G'' = ''K''₂. # Δ(''G'') ≤ 2 δ(''G''). # Δ(''G'') ≤ n/2 + 1. Here χ″(''G'') is the total chromatic number; Δ(''G'') is the

maximum degree This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...

; and δ(''G'') is the minimum degree.

Notes

References

*. *. *. *. *. *. *. *. *. *. *. *. *. As cited by . *. *. As cited by .

External links

*{{mathworld, title=Uniquely Colorable Graph, id=UniquelyColorableGraph, mode=cs2 Graph coloring