Uniquely colorable graph
Encyclopedia
In graph theory
, a uniquely colorable graph is a k-chromatic
graph that has only one possible (proper) k-coloring
up to permutation of the colors.
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 graphs are known to be exactly the Apollonian network
s, that is, the planar 3-trees .
. The deletion of any vertex from a minimal imperfect graph leaves a uniquely colorable subgraph.
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
K1,k are uniquely k-edge-colorable graphs. 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. The generalized Petersen graph
G(9,2) is the only known nonplanar
uniquely 3-edge-colorable graph, and it has been conjectured that it is the only such graph. See and .
that has only one possible (proper) k-total-coloring
up to permutation of the colors.
Empty graphs, 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:
Here χ″(G) is the total chromatic number
; Δ(G), maximum degree; and δ(G), minimum degree.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a uniquely colorable graph is a k-chromatic
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
graph that has only one possible (proper) k-coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
up to permutation of the colors.
Examples
A complete graphComplete 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.-Properties:...
is uniquely colorable, because the only proper coloring is one that assigns each vertex a different color.
Every k-tree
K-tree
In graph theory, a k-tree is a chordal graph all of whose maximal cliques are the same size k + 1 and all of whose minimal clique separators are also all the same size k....
is uniquely (k + 1)-colorable. The uniquely 4-colorable planar graphs are known to be exactly the Apollonian network
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 maximal planar chordal graphs, the uniquely 4-colorable...
s, that is, the planar 3-trees .
Properties
Some properties of a uniquely k-colorable graph G with n vertices and m edges:- m ≥ (k - 1) n - k(k-1)/2.
Minimal imperfection
A minimal imperfect graph is a graph in which every subgraph is perfectPerfect graph
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....
. 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-chromaticEdge coloring
In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...
graph that has only one possible (proper) k-edge-coloring
Edge coloring
In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...
up to permutation of the colors. The only uniquely 2-edge-colorable graphs are the paths and the cycles. For any k, the stars
Star (graph theory)
In graph theory, a star Sk is the complete bipartite graph K1,k: a tree with one internal node and k leaves...
K1,k are uniquely k-edge-colorable graphs. 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. The generalized Petersen graph
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 of constructing the Petersen graph. The generalized...
G(9,2) is the only known nonplanar
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...
uniquely 3-edge-colorable graph, and it has been conjectured that it is the only such graph. See and .
Unique total colorability
A uniquely total colorable graph is a k-total-chromatic graphTotal coloring
In graph theory, total coloring is a type of coloring on the vertices and edges of a graph.When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent vertices, no adjacent edges, and no edge and its endvertices are assigned the same color.The...
that has only one possible (proper) k-total-coloring
Total coloring
In graph theory, total coloring is a type of coloring on the vertices and edges of a graph.When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent vertices, no adjacent edges, and no edge and its endvertices are assigned the same color.The...
up to permutation of the colors.
Empty graphs, paths
Path graph
In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
, and cycles
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
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 = K2.
- Δ(G) ≤ 2 δ(G).
- Δ(G) ≤ n/2 + 1.
Here χ″(G) is the total chromatic number
Total coloring
In graph theory, total coloring is a type of coloring on the vertices and edges of a graph.When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent vertices, no adjacent edges, and no edge and its endvertices are assigned the same color.The...
; Δ(G), maximum degree; and δ(G), minimum degree.