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.

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]

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]

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.

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]

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 ₂ . ^[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 .

• Akbari, S. (2003), "Dos conjeturas sobre grafos totalmente coloreables de forma única", Discrete Mathematics , 266 (1–3): 41–45, doi : 10.1016/S0012-365X(02)00797-5 , MR  1991705.
• Akbari, S.; Behzad, M.; Hajiabolhassan, H.; Mahmoodian, ES (1997), "Gráficos coloreables de forma única y total", Graphs and Combinatorics , 13 (4): 305–314, doi : 10.1016/S0012-365X(02)00797-5 , MR  1485924.
• belcastro, sarah-marie ; Haas, Ruth (2015), "Gráficos cúbicos de tres aristas coloreables sin triángulos", Contribuciones a las matemáticas discretas , 10 (2): 39–44, arXiv : 1508.06934 , doi : 10.11575/cdm.v10i2.62320 , MR  3499076.
• Bollobás, Béla (1978), Teoría de grafos extremos , LMS Monographs, vol. 11, Academic Press, MR  0506522.
• Fowler, Thomas (1998), Unique Coloring of Planar Graphs (PDF) , tesis doctoral, Departamento de Matemáticas del Instituto Tecnológico de Georgia.
• Hillar, Christopher J.; Windfeldt, Troels (2008), "Caracterización algebraica de grafos coloreables con vértices únicos", Journal of Combinatorial Theory , Serie B, 98 (2): 400–414, arXiv : math/0606565 , doi :10.1016/j.jctb.2007.08.004, MR  2389606, S2CID  108304.
• Mahmoodian, ES (1998), "Definición de conjuntos y unicidad en coloraciones de gráficos: una encuesta", Journal of Statistical Planning and Inference , 73 (1–2): 85–89, doi :10.1016/S0378-3758(98)00053-6, MR  1655213.
• Mahmoodian, ES; Shokrollahi, MA (1995), "Problemas abiertos en el taller de combinatoria de AIMC25 (Teherán, 1994)", en CJ, Colbourn ; ES, Mahmoodian (eds.), Combinatorics Advances , Mathematics and its applications, vol. 329, Dordrecht; Boston; Londres: Kluwer Academic Publishers, págs. 321–324.
• Schwenk, Allen J. (1989), "Enumeración de ciclos hamiltonianos en ciertos grafos de Petersen generalizados", Journal of Combinatorial Theory , Serie B, 47 (1): 53–59, doi : 10.1016/0095-8956(89)90064-6 , MR  1007713.
• Thomason, AG (1978), "Ciclos hamiltonianos y grafos con aristas coloreables de forma única", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977) , Annals of Discrete Mathematics, vol. 3, págs. 259-268, MR  0499124.
• Thomason, Andrew (1982), "Los gráficos cúbicos con tres ciclos hamiltonianos no siempre son coloreables de manera única por sus bordes", Journal of Graph Theory , 6 (2): 219–221, doi :10.1002/jgt.3190060218, MR  0655209.
• Truszczyński, M. (1984), "Algunos resultados sobre grafos coloreables de forma única", en Hajnal, A. ; Lovász, L. ; Sós, VT (eds.), Conjuntos finitos e infinitos. Vol. I, II. Actas del sexto coloquio combinatorio húngaro celebrado en Eger, del 6 al 11 de julio de 1981 , Colloq. Math. Soc. János Bolyai, vol. 37, Holanda Septentrional, Ámsterdam, págs. 733–748, MR  0818274.
• Tutte, William T. (1976), "Circuitos hamiltonianos", Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo I , Accad. Naz. Lincei, Roma, págs. 193-199. Atti dei Convegni Lincei, nº 17, MR  0480185Como citan belcastro y Haas (2015).
• Xu, Shao Ji (1990), "El tamaño de los gráficos coloreables de forma única", Journal of Combinatorial Theory , Serie B, 50 (2): 319–320, doi : 10.1016/0095-8956(90)90086-F , MR  1081235.
• Wilson, RJ (1976), "Problema 2", en Nash-Williams, C. St. JA ; Sheehan, J. (eds.), Proc. British Comb. Conf. 1975 , Winnipeg: Utilitas Math., pág. 696Como lo cita Thomason (1978).

• Weisstein, Eric W. , "Gráficos de colores únicos", MathWorld