Přesné zbarvení - Exact coloring

Příklad přesného zbarvení se 7 barvami a 14 vrcholy

v teorie grafů, an přesné zbarvení je (správné) zbarvení vrcholů ve kterém se každá dvojice barev objeví přesně na jednom páru sousedních vrcholů. To znamená, že jde o a rozdělit vrcholů grafu do disjunktních nezávislé sady tak, že pro každou dvojici odlišných nezávislých sad v oddílu existuje přesně jedna hrana s koncovými body v každé sadě.^[1][2]

Kompletní grafy, oddíly a Eulerovy prohlídky

Přesné vybarvení kompletní graf K.₆

Každý n-vrchol kompletní graf K._n má přesné zbarvení pomocí n barvy, získané přidělením každého vrcholu jinou barvou. Každý graf s n-barevné přesné zbarvení lze získat jako a oddělení úplného grafu, graf získaný z úplného grafu rozdělením každého vrcholu do nezávislé množiny a opětovným připojením každého okrajového incidentu k vrcholu přesně k jednomu z členů odpovídající nezávislé sady.^[1][2]

Když k je liché číslo „Cesta nebo cyklus s ${ displaystyle { tbinom {k} {2}}}$ hrany má přesné zbarvení, které se získá vytvořením přesného vybarvení celého grafu K._k a pak najít Prohlídka Euler tohoto úplného grafu. Například cesta se třemi okraji má kompletní 3 zbarvení.^[2]

Související typy zbarvení

Přesné zbarvení úzce souvisí s harmonické barvy (barviva, ve kterých se každá dvojice barev objeví maximálně jednou) a kompletní barvení (barviva, ve kterých se každá dvojice barev objeví alespoň jednou). Je jasné, že přesné zbarvení je zbarvení, které je harmonické i úplné. Graf G s n vrcholy a m hrany má harmonický k-barvení právě tehdy ${ displaystyle m leq { tbinom {k} {2}}}$ a graf vytvořený z G přidáváním ${ displaystyle { tbinom {k} {2}} - m}$ izolované hrany mají přesné zabarvení. Graf G se stejnými parametry má kompletní k-barvení právě tehdy ${ displaystyle m geq { tbinom {k} {2}}}$ a existuje podgraf H z G s přesným k-barvení, ve kterém každý okraj G − H má koncové body různých barev. Potřeba stavu na okrajích G − H je ukázán na příkladu cyklu čtyř vrcholů, který má podgraf s přesným 3-zbarvením (cesta se třemi okraji), ale sám nemá úplné 3-zbarvení.^[2]

Výpočetní složitost

to je NP-kompletní určit, zda má daný graf přesné zbarvení, a to i v případě, že je graf a strom.^[1][3] Problém však může být vyřešen v polynomiální čas pro stromy ohraničené stupeň.^[1][4]

Reference