Subcoloración

Una subcoloración no óptima con cuatro colores. Al combinar los colores rojo y azul, y los colores verde y amarillo, se obtiene una subcoloración con solo dos colores.

En teoría de grafos , una subcoloración es una asignación de colores a los vértices de un grafo de modo que cada clase de color induzca una unión disjunta de vértices de camarillas . Es decir, cada clase de color debería formar un grafo de clúster .

El número subcromático χ _S ( G ) de un grafo G es la menor cantidad de colores necesarios en cualquier subcoloración de G .

La subcoloración y el número subcromático fueron introducidos por Albertson et al. (1989).

Toda coloración propia y cocoloración de un grafo son también subcoloraciones, por lo que el número subcromático de cualquier grafo es como máximo igual al número cocromático, que es como máximo igual al número cromático.

La subcoloración es tan difícil de resolver exactamente como la coloración, en el sentido de que (al igual que la coloración) es NP-completo . Más específicamente, el problema de determinar si un grafo plano tiene un número subcromático de como máximo 2 es NP-completo, incluso si es un

• grafo libre de triángulos con grado máximo 4 (Gimbel & Hartman 2003) (Fiala et al. 2003),
• gráfico de comparabilidad con grado máximo 4 (Ochem 2017),
• gráfico lineal de un grafo bipartito con grado máximo 4 (Gonçalves & Ochem 2009),
• gráfico con circunferencia 5 (Montassier y Ochem 2015).

El número subcromático de un cografo se puede calcular en tiempo polinómico (Fiala et al. 2003). Para cada entero fijo r, es posible decidir en tiempo polinómico si el número subcromático de los grafos de intervalo y de permutación es como máximo r (Broersma et al. 2002).

Referencias

• Albertson, MO; Jamison, RE; Hedetniemi, ST; Locke, SC (1989), "El número subcromático de un gráfico", Discrete Mathematics , 74 (1–2): 33–49, doi : 10.1016/0012-365X(89)90196-9.
• Broersma, Hajo; Fomin, Fedor V.; Nesetril, Jaroslav; Woeginger, Gerhard (2002), "Más sobre subcoloraciones" (PDF) , Computing , 69 (3): 187–203, doi :10.1007/s00607-002-1461-1, S2CID  24777938.
• Fiala, J.; Klaus, J.; Le, VB; Seidel, E. (2003), "Subcoloraciones de grafos: complejidad y algoritmos", SIAM Journal on Discrete Mathematics , 16 (4): 635–650, CiteSeerX  10.1.1.3.183 , doi :10.1137/S0895480101395245.
• Gimbel, John; Hartman, Chris (2003), "Subcoloraciones y el número subcromático de un gráfico", Discrete Mathematics , 272 (2–3): 139–154, doi : 10.1016/S0012-365X(03)00177-8.
• Gonçalves, Daniel; Ochem, Pascal (2009), "Sobre la arboricidad de las estrellas y las orugas", Discrete Mathematics , 309 (11): 3694–3702, doi : 10.1016/j.disc.2008.01.041.
• Montassier, Mickael; Ochem, Pascal (2015), "Coloraciones casi coloreables: gráficos no coloreables y NP-completitud", Electronic Journal of Combinatorics , 22 (1): #P1.57, arXiv : 1306.0752 , doi :10.37236/3509, S2CID  59507.
• Ochem, Pascal (2017), "La subcoloración de 2 colores es NP-completa para gráficos de comparabilidad plana", Information Processing Letters , 128 : 46–48, arXiv : 1702.01283 , doi : 10.1016/j.ipl.2017.08.004, S2CID  22108461.