En la teoría de grafos , un grafo de coloración única es un grafo cromático k que solo tiene un color k posible (adecuado) 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 de
Un gráfico completo se puede colorear de forma única, porque el único color adecuado es el que asigna a cada vértice un color diferente.
Cada árbol k es únicamente ( k + 1) -colorable. Se sabe que los gráficos planos de 4 colores únicos son exactamente las redes apolíneas , es decir, los 3 árboles planos ( Fowler 1998 ).
Propiedades
Algunas propiedades de un grafo G singularmente k -colorable con n vértices y m aristas:
- m ≥ ( k - 1) norte - k ( k -1) / 2. ( Truszczyński 1984 ; Xu 1990 )
Conceptos relacionados
Imperfección mínima
Un gráfico mínimo imperfecto es un gráfico en el que cada subgráfico es perfecto . La supresión de cualquier vértice de un gráfico mínimo imperfecto deja un subgráfico de color único.
Coloración de borde única
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/3/3a/Generalized_Petersen_9_2_edge_coloring.svg/220px-Generalized_Petersen_9_2_edge_coloring.svg.png)
Un gráfico de color de borde único es un gráfico cromático de borde k que solo tiene un color de borde k (adecuado) posible hasta la permutación de los colores. Los únicos gráficos que se pueden colorear de forma única en dos bordes son las trayectorias y los ciclos. Para cualquier k , las estrellas K 1, k son únicamente k de color en el borde. 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 gráficos que se pueden colorear de forma única de 3 bordes que no encajan en esta clasificación, como el gráfico de la pirámide triangular .
Si un gráfico cúbico es únicamente colorable en 3 bordes, debe tener exactamente tres ciclos hamiltonianos , formados por los bordes con dos de sus tres colores, pero algunos gráficos cúbicos con solo tres ciclos hamiltonianos no son únicamente coloreables en 3 bordes ( Thomason 1982 ). Cada grafo cúbico plano simple que se puede colorear de forma única en 3 aristas contiene un triángulo ( Fowler 1998 ), pero WT Tutte ( 1976 ) observó que el grafo de Petersen generalizado G (9,2) es no plano , libre de triángulos y únicamente Colorante en 3 bordes. Durante muchos años fue el único gráfico conocido de este tipo, y se había conjeturado que era el único gráfico de este tipo (véanse Bollobás 1978 y Schwenk 1989 ), pero ahora se conocen infinitas gráficas cúbicas no planas libres de triángulos con coloración única de 3 aristas. ( belcastro y Haas 2015 ).
Colorabilidad total única
Un gráfico de coloración total único es un gráfico k -total-cromático que solo tiene un k -total-colorante posible (adecuado) hasta la permutación de los colores.
Los gráficos vacíos , las rutas y los ciclos de longitud divisible por 3 son gráficos coloreables únicamente totales. Mahmoodian y Shokrollahi (1995) conjeturaron que también son los únicos miembros de esta familia.
Algunas propiedades de un grafo G únicamente con k -totalmente coloreable con n vértices:
- χ ″ ( G ) = Δ ( G ) + 1 a menos que G = K 2 . ( Akbari et al. 1997 )
- Δ ( G ) ≤ 2 δ ( G ). ( Akbari et al. 1997 )
- Δ ( G ) ≤ n / 2 + 1. ( Akbari 2003 )
Aquí χ ″ ( G ) es el número cromático total ; Δ ( G ) es el grado máximo ; y δ ( G ) es el grado mínimo .
Referencias
- Akbari, S. (2003), "Dos conjeturas sobre gráficos exclusivamente coloreables", Matemáticas discretas , 266 (1-3): 41-45, doi : 10.1016 / S0012-365X (02) 00797-5 , MR 1991705.
- Akbari, S .; Behzad, M .; Hajiabolhassan, H .; Mahmoodian, ES (1997), "Uniquely total colorable graphs", 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 coloreables de tres bordes sin triángulos", Contribuciones a las matemáticas discretas , 10 (2): 39–44, arXiv : 1508.06934 , Bibcode : 2015arXiv150806934B , MR 3499076.
- Bollobás, Béla (1978), Extremal Graph Theory , LMS Monographs, 11 , Academic Press, MR 0506522.
- Fowler, Thomas (1998), Coloración única de gráficos planos (PDF) , Ph.D. tesis, Departamento de Matemáticas del Instituto de Tecnología de Georgia.
- Hillar, Christopher J .; Windfeldt, Troels (2008), "Caracterización algebraica de gráficos coloreables de vértice único", Journal of Combinatorial Theory , Serie B, 98 (2): 400–414, arXiv : math / 0606565 , doi : 10.1016 / j.jctb.2007.08. 004 , MR 2389606.
- Mahmoodian, ES; Shokrollahi, MA (1995), "Problemas abiertos en el taller de combinatoria de AIMC25 (Teherán, 1994)", en CJ, Colbourn ; ES, Mahmoodian (eds.), Avances combinatorios , Matemáticas y sus aplicaciones, 329 , Dordrecht; Bostón; Londres: Kluwer Academic Publishers, págs. 321–324.
- Schwenk, Allen J. (1989), "Enumeración de ciclos hamiltonianos en ciertos gráficos 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 gráficos con colores de bordes únicos", Advances in Graph Theory (Conf. Combinatoria de Cambridge, Trinity College, Cambridge, 1977) , Annals of Discrete Mathematics, 3 , págs. 259-268, MR 0499124.
- Thomason, Andrew (1982), "Las gráficas cúbicas con tres ciclos hamiltonianos no siempre son únicamente coloreables en los bordes", Journal of Graph Theory , 6 (2): 219-221, doi : 10.1002 / jgt.3190060218 , MR 0655209.
- Truszczyński, M. (1984), "Algunos resultados en gráficos de colores únicos", en Hajnal, A .; Lovász, L .; Sós, VT (eds.), Conjuntos finitos e infinitos. Vol. Yo, II. Actas del sexto coloquio combinatorio húngaro celebrado en Eger, del 6 al 11 de julio de 1981 , Coloq. Matemáticas. Soc. János Bolyai, 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, No. 17, MR 0480185. Según lo citado por belcastro y Haas (2015) .
- Xu, Shao Ji (1990), "El tamaño de los gráficos con colores únicos", 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. Peine británico. Conf. 1975 , Winnipeg: Utilitas Math., Pág. 696. Como lo cita Thomason (1978) .
enlaces externos
- Weisstein, Eric W. "Gráfico singularmente k-colorable" . MathWorld .