Cocoloring
En la teoría de grafos , un cocoloring de un gráfico G es una asignación de colores a los vértices de tal manera que cada clase de color forma un conjunto independiente en G o en el complemento de G . El número cochromatic z ( G ) de G es los colores menor número necesarias en cualquier cocolorings de G . Los gráficos con número cocromático 2 son exactamente los gráficos bipartitos , los complementos de los gráficos bipartitos y los gráficos divididos .
Como el requisito de que cada clase de color sea una camarilla o independiente es más débil que el requisito de colorear (en el que cada clase de color debe ser un conjunto independiente) y más fuerte que para el subcoloring (en el que cada clase de color debe ser una unión disjunta de camarillas) , se deduce que el número cochromatic de G es menor que o igual que el número cromático de G , y que es mayor que o igual al número subchromatic de G .
El cocoloring fue nombrado y estudiado por primera vez por Lesniak & Straight (1977) . Jørgensen (1995) caracteriza gráficos 3-cocromáticos críticos, mientras que Fomin, Kratsch y Novelli (2002) describen algoritmos para aproximar el número cocromático de un gráfico. Zverovich (2000) define una clase de gráficos cocromáticos perfectos , análoga a la definición de gráficos perfectos mediante la coloración de gráficos, y proporciona una caracterización subgráfica prohibida de estos gráficos.
Referencias
- Fomin, Fedor V .; Kratsch, Dieter; Novelli, Jean-Christophe (2002), "Aproximación de los colores mínimos", Inf. Proceso. Letón. , 84 (5): 285–290, doi : 10.1016 / S0020-0190 (02) 00288-0.
- Gimbel, John; Straight, H. Joseph (1987), "Algunos temas de la teoría cocromática", Gráficos y combinatoria , 3 (1): 255-265, doi : 10.1007 / BF01788548.
- Jørgensen, Leif K. (1995), " Gráficos 3 cocromáticos críticos", Gráficos y combinatoria , 11 (3): 263–266, doi : 10.1007 / BF01793013.
- Lesniak, L .; Straight, HJ (1977), "El número cocromático de un gráfico", Ars Combinatoria , 3 : 39–46.
- Straight, HJ (1979), "Número cocromático y el género de un gráfico", Journal of Graph Theory , 3 (1): 43–51, doi : 10.1002 / jgt.3190030106.
- Zverovich, Igor V. (2000), Perfect gráficos cochromatic , Investigación informe RRR 16-2000, Centro de la Universidad de Rutgers para Investigación de Operaciones, Archivado desde el original en 03/03/2016 , recuperada 2006-10-16.
