Barvení - Cocoloring

Barvení 3 barvami (obrázek vlevo nahoře): a správně Trojbarevnost tohoto grafu je nemožná. Modrá podgraf tvoří a klika (obrázek vpravo dole), zatímco červené a zelené podgrafy tvoří kliky na grafech doplněk.

v teorie grafů, a barvení grafu G je úkolem barvy k vrcholům tak, aby každá barevná třída tvořila nezávislá sada v G nebo v doplněk z G. The kochromatické číslo z (G) z G je nejméně barev potřebných pro jakékoli zbarvení G. Grafy s kochromatickým číslem 2 jsou přesně ty bipartitní grafy, doplňuje bipartitní grafy a rozdělené grafy.

Protože požadavek, aby každá barevná třída byla kliková nebo nezávislá, je slabší než požadavek pro zbarvení (ve kterém musí být každá barevná třída nezávislou sadou) a silnější než pro podbarvení (ve kterém každá barevná třída musí být disjunktním spojením klik), z toho vyplývá, že kochromatický počet G je menší nebo rovno chromatické číslo z G, a že je větší nebo rovno subchromatickému počtu G.

Cocoloring byl pojmenován a nejprve studován Lesniak & Straight (1977). Jørgensen (1995) charakterizuje kritické 3-kochromatické grafy, zatímco Fomin, Kratsch & Novelli (2002) popsat algoritmy pro aproximaci kochromatického čísla grafu. Zverovich (2000) definuje třídu dokonalé kochromatické grafy, analogický s definicí dokonalých grafů pomocí zbarvení grafu, a poskytuje zakázanou subgrafickou charakterizaci těchto grafů.

Reference

  • Fomin, Fedor V .; Kratsch, Dieter; Novelli, Jean-Christophe (2002), "Přibližné minimální zabarvení", Inf. Proces. Lett., 84 (5): 285–290, doi:10.1016 / S0020-0190 (02) 00288-0.
  • Gimbel, John; Straight, H. Joseph (1987), „Některá témata v kochromatické teorii“, Grafy a kombinatorika, 3 (1): 255–265, doi:10.1007 / BF01788548.
  • Jørgensen, Leif K. (1995), „Critical 3-cochromatic graphs“, Grafy a kombinatorika, 11 (3): 263–266, doi:10.1007 / BF01793013.
  • Lesniak, L .; Straight, H. J. (1977), „The cochromatic number of a graph“, Ars Combinatoria, 3: 39–46.
  • Straight, H. J. (1979), "Cochromatic number and the gen of a graph", Journal of Graph Theory, 3 (1): 43–51, doi:10,1002 / jgt.3190030106.
  • Zverovich, Igor V. (2000), Dokonalé kochromatické grafy „Výzkumná zpráva RRR 16-2000, Rutgers University Center for Operations Research, archivováno z originál dne 03.03.2016, vyvoláno 2006-10-16.