stringtranslate.com

Gráfico único en color

En teoría de grafos , un grafo coloreable de forma única es un grafo k -cromático que tiene solo una coloración k posible (adecuada) hasta la permutación de los colores . De manera equivalente, solo hay una forma de dividir sus vértices en k conjuntos independientes y no hay forma de dividirlos en k − 1 conjuntos independientes.

Ejemplos

Un gráfico completo es coloreable de manera única, porque la única coloración adecuada es aquella que asigna a cada vértice un color diferente.

Cada árbol k es coloreable de forma única ( k + 1). Se sabe que los gráficos planares  coloreables de forma única son exactamente las redes apolíneas , es decir, los 3-árboles planares. [1]

Cada grafo bipartito conectado es de forma única bicolorizable. Su bicolorización se puede obtener eligiendo un vértice inicial arbitrariamente, coloreando los vértices a una distancia par del vértice inicial con un color y coloreando los vértices a una distancia impar del vértice inicial con el otro color. [2]

Propiedades

Un grafo G de k colores únicos con n vértices tiene al menos m ≥ ( k −1) n − k ( k −1)/2 aristas. La igualdad se cumple cuando G es un ( k −1) -árbol. [3]

Conceptos relacionados

Imperfección mínima

Un grafo imperfecto mínimo es un grafo en el que cada subgrafo es perfecto . La eliminación de cualquier vértice de un grafo imperfecto mínimo deja un subgrafo coloreable de manera única.

Coloración única de los bordes

La coloración única de tres aristas del gráfico generalizado de Petersen G (9,2)

Un grafo de aristas cromáticas de k aristas es un grafo de aristas cromático que tiene solo una coloración de aristas k posible (adecuada) hasta la permutación de los colores. Los únicos grafos de aristas cromáticas de 2 aristas son los caminos y los ciclos. Para cualquier k , las estrellas K 1, k son de aristas cromáticas de k de manera única. Además, Wilson (1976) conjeturó y Thomason (1978) demostró que, cuando k ≥ 4, también son los únicos miembros de esta familia. Sin embargo, existen grafos de aristas cromáticas de 3 aristas que no encajan en esta clasificación, como el grafo de la pirámide triangular .

Si un grafo cúbico es coloreable únicamente por sus 3 aristas, debe tener exactamente tres ciclos hamiltonianos , formados por las aristas con dos de sus tres colores, pero algunos grafos cúbicos con solo tres ciclos hamiltonianos no son coloreables únicamente por sus 3 aristas. [4] Todo grafo cúbico plano simple que es coloreable únicamente por sus 3 aristas contiene un triángulo, [1] pero WT Tutte  (1976) observó que el grafo Petersen generalizado G (9,2) no es plano , no tiene triángulos y es coloreable únicamente por sus 3 aristas. Durante muchos años fue el único grafo conocido de ese tipo, y se había conjeturado que era el único de ese tipo [5] pero ahora se conocen infinitos grafos cúbicos no planos sin triángulos coloreables únicamente por sus 3 aristas. [6]

Colorabilidad total única

Un gráfico coloreable total único es un gráfico k -total-cromático que tiene solo una coloración k -total posible (adecuada) hasta la permutación de los colores.

Los gráficos vacíos , las trayectorias y los ciclos de longitud divisible por 3 son gráficos coloreables totales únicos. Mahmoodian y Shokrollahi (1995) conjeturaron que también son los únicos miembros de esta familia.

Algunas propiedades de un gráfico G de k -totalmente coloreable con n vértices:

  1. χ″( G ) = Δ( G ) + 1 a menos que G = K 2 . [7]
  2. Δ( G ) ≤ 2 δ( G ). [7]
  3. Δ( G ) ≤ n/2 + 1. [8]

Aquí χ″( G ) es el número cromático total ; Δ( G ) es el grado máximo ; y δ( G ) es el grado mínimo .

Notas

  1. ^Por Fowler (1998).
  2. ^ Mahmoodian (1998).
  3. ^ Truszczyński (1984); Xu (1990).
  4. ^ Thomason (1982).
  5. ↑ Bollobás (1978); Schwenk (1989).
  6. ^ belcastro y Haas (2015).
  7. ^ desde Akbari y col. (1997).
  8. ^ Agosto (2003).

Referencias

Enlaces externos