Subcoloración

En teoría de grafos , una subcoloración es una asignación de colores a los vértices de un grafo de tal manera que cada clase de color induce una unión disjunta de cliques . Es decir, cada clase de color debe 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) .

Cada coloración propia y cada cocoloración de un gráfico son también subcoloraciones, por lo que el número subcromático de cualquier gráfico es como máximo igual al número cocromático, que a su vez 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-completa . Más específicamente, el problema de determinar si un grafo planar tiene un número subcromático como máximo 2 es NP-completo, incluso si es un

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

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

• Albertson, MO; Jamison, RE; Hedetniemi, ST; Locke, SC (1989), "El número subcromático de un grafo", Matemáticas Discretas , 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), "Graph Subcolorings: Complexity and Algorithms", 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 grafo", Matemáticas Discretas , 272 ( 2–3 ): 139–154 , doi : 10.1016/S0012-365X(03)00177-8.
• Gonçalves, Daniel; Ochem, Pascal (2009), "Sobre la arboricidad estrellada y oruga", Matemáticas Discretas , 309 (11): 3694– 3702, doi : 10.1016/j.disc.2008.01.041.
• Montassier, Mickael; Ochem, Pascal (2015), "Near-Colorings: Non-Colorable Graphs and NP-Completeness" , Electronic Journal of Combinatorics , 22 (1): #P1.57, arXiv : 1306.0752 , doi : 10.37236/3509 , S2CID 59507 .
• Ochem, Pascal (2017), "El 2-subcoloring es NP-completo para grafos de comparabilidad planares", Information Processing Letters , 128 : 46–48 , arXiv : 1702.01283 , doi : 10.1016/j.ipl.2017.08.004 , S2CID 22108461 .