En la teoría de grafos , un subcoloring es una asignación de colores a los vértices de un grafo de manera que cada clase de color induce una unión disjunta de vértices de grupos . Es decir, cada clase de color debe formar un gráfico de grupo .
El número subchromatic χ S ( G ) de un gráfico G es los colores menor número necesarias en cualquier subcoloring de G .
Subcoloring y número subchromatic fueron introducidos por Albertson et al. (1989) .
Todas las coloraciones y cocolorizaciones adecuadas de un gráfico también son subcoloraciones, por lo que el número subcromático de cualquier gráfico es como máximo igual al número cocromático, que es como máximo igual al número cromático.
Subcoloring es tan difícil de resolver exactamente como colorear, en el sentido de que (como colorear) es NP-completo . Más específicamente, el problema de determinar si un gráfico plano tiene un número subcromático como máximo 2 es NP-completo, incluso si es un
- gráfico 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 lineal de un gráfico bipartito con grado máximo 4 ( Gonçalves & Ochem 2009 ),
- gráfico con circunferencia 5 ( Montassier & Ochem 2015 ).
El número subcromático de una cografía se puede calcular en tiempo polinomial ( Fiala et al. 2003 ). Para cada entero fijo r, es posible decidir en tiempo polinómico si el número subcromático de intervalos y gráficos 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 una gráfica", 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 subcoloridos", Computación , 69 (3): 187–203, doi : 10.1007 / s00607-002-1461-1.
- 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), "Subcolorings and the subchromatic number of a graph", Discrete Mathematics , 272 (2-3): 139-154, doi : 10.1016 / S0012-365X (03) 00177-8.
- Gonçalves, Daniel; Ochem, Pascal (2009), "On star and caterpillar arboricity", Discrete Mathematics , 309 (11): 3694–3702, doi : 10.1016 / j.disc.2008.01.041.
- Montassier, Mickael; Ochem, Pascal (2015), "Casi colorantes: Gráficos no coloreables y NP-Completeness" , Revista electrónica de combinatoria , 22 (1): # P1.57.
- Ochem, Pascal (2017), "2-subcoloring is NP-complete para gráficos de comparabilidad plana", Information Processing Letters , 128 : 46–48, arXiv : 1702.01283 , doi : 10.1016 / j.ipl.2017.08.004.