¿Qué se sabe sobre los grafos que permiten solo una coloración?

Question

Algunos gráficos ($K_n$ o $K_n$ menos cualquier arista, por ejemplo) solo permiten una coloración mínima hasta diferentes etiquetas de los colores. ¿Se sabe algo sobre este tipo de gráficos? Puedo pensar en varios ejemplos de tales gráficos (principalmente solo $K_{n,m}$ menos una o dos aristas), pero no puedo pensar en ninguna afirmación general que pueda hacer sobre ellos.

Solo estaba preguntándome si existía alguna investigación previa sobre esto, ya que no pude encontrar nada. Podría ser que sea trivial (en cuyo caso estaría interesado en saber si se sabe algo sobre el número de coloraciones mínimas).

Answer 1

Es un poco difícil dar una respuesta exhaustiva sin saber exactamente qué tipo de propiedades estás buscando, pero aquí hay un comienzo. Estos grafos se llaman grafos coloreables de forma única (ver aquí y aquí). Para el caso de dos colores, se caracterizan como grafos bipartitos conectados, pero para un número mayor de colores no se conoce tal caracterización.

En un grafo de forma única $k$-coloreable, con $n$ vértices, el número de aristas es al menos $(k-1)n-\binom{k}{2}$, pero de lo contrario no tienen que ser extremadamente densos como sugieren tus ejemplos. De hecho, para cualquier $n$ existen grafos con $n$ vértices que son coloreables de forma única con 3 colores y no tienen triángulos. El límite inferior para el número de aristas se logra en cualquier $(k-1)$-árbol (alternativamente un grafo maximal de treewidth $k-1$).