Skip to main content
added 173 characters in body
Source Link
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

It's a bit hard to give a comprehensive answer without knowing exactly what sort of properties you are after, but here is a start. Such graphs are called uniquely colorable graphs (see here and here). For the case of two colors they are characterized as the connected bipartite graphs, but for higher numbers of colors no such characterization is known.

In a uniquely $k$-colorable graph of $n$ vertices, the number of edges is at least $(k-1)n-\binom{k}{2}$, but otherwise they don't have to be extremely dense as your examples suggest. In fact for any $n$ there exist graphs with $n$ vertices that are uniquely 3-colorable and have no triangles. The lower bound for the number of edges is achieved at any $(k-1)$-tree (alternatively maximal graph of treewidth $k-1$).

It's a bit hard to give a comprehensive answer without knowing exactly what sort of properties you are after, but here is a start. Such graphs are called uniquely colorable graphs (see here and here). For the case of two colors they are characterized as the connected bipartite graphs, but for higher numbers of colors no such characterization is known.

In a uniquely $k$-colorable graph of $n$ vertices, the number of edges is at least $(k-1)n-\binom{k}{2}$, but otherwise they don't have to be extremely dense as your examples suggest. In fact for any $n$ there exist graphs with $n$ vertices that are uniquely 3-colorable and have no triangles.

It's a bit hard to give a comprehensive answer without knowing exactly what sort of properties you are after, but here is a start. Such graphs are called uniquely colorable graphs (see here and here). For the case of two colors they are characterized as the connected bipartite graphs, but for higher numbers of colors no such characterization is known.

In a uniquely $k$-colorable graph of $n$ vertices, the number of edges is at least $(k-1)n-\binom{k}{2}$, but otherwise they don't have to be extremely dense as your examples suggest. In fact for any $n$ there exist graphs with $n$ vertices that are uniquely 3-colorable and have no triangles. The lower bound for the number of edges is achieved at any $(k-1)$-tree (alternatively maximal graph of treewidth $k-1$).

Source Link
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

It's a bit hard to give a comprehensive answer without knowing exactly what sort of properties you are after, but here is a start. Such graphs are called uniquely colorable graphs (see here and here). For the case of two colors they are characterized as the connected bipartite graphs, but for higher numbers of colors no such characterization is known.

In a uniquely $k$-colorable graph of $n$ vertices, the number of edges is at least $(k-1)n-\binom{k}{2}$, but otherwise they don't have to be extremely dense as your examples suggest. In fact for any $n$ there exist graphs with $n$ vertices that are uniquely 3-colorable and have no triangles.