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 conne ...

, 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 proc ...

of the colors. Equivalently, there is only one way to

partition Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of a ...

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 c ...

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 cross ...

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 maxima ...

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 are ...

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. 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 held together by its gravity. The nearest star to Earth is the Sun. Many other stars are visible to the naked eye at night, but their immense distances from Earth ma ...

''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 o ...

. 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 ...

''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 th ...

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; 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