Silné zbarvení - Strong coloring

Tento Möbiový žebřík je silně 4barevný. Existuje 35 oddílů o velikosti 4, ale pouze těchto 7 oddílů je topologicky odlišných.

v teorie grafů, a silné zbarvení, s ohledem na rozdělení vrcholů do (disjunktních) podmnožin stejné velikosti, je a (správné) zbarvení vrcholů ve kterém se každá barva v každé části objeví přesně jednou. Graf je silně k-barevné if, for each partition of the vertices into sets of size k, připouští silné zbarvení. Když objednat grafu G není dělitelné k, přidali jsme izolované vrcholy na G dost na to, aby bylo pořadí nového grafu G' dělitelné k. V takovém případě silné zbarvení G' minus dříve přidané izolované vrcholy se považují za silné zbarvení G. [1]

The silné chromatické číslo sχ (G) grafu G je nejméně k takhle G je silně k-barevný. Graf je silně k-chromatický pokud má silné chromatické číslo k.

Některé vlastnosti sχ (G):

  1. sχ (G)> Δ (G).
  2. sχ (G) ≤ 3 Δ (G) − 1.[2]
  3. Asymptoticky, sχ (G) ≤ 11 Δ (G) / 4 + o (Δ (G)).[3]

Zde Δ (G) je maximální stupeň.

Silné chromatické číslo nezávisle zavedl Alon (1988)[4][5] and Fellows (1990).[6]

Související problémy

Vzhledem k tomu, graf a rozdělení vrcholů, an nezávislý příčný je sada U nesousedících vrcholů tak, že každá část obsahuje přesně jeden vrchol U. Silné vybarvení je ekvivalentní rozdělení vrcholů na disjunktní nezávislé-příčné (každý nezávislý-příčný je jedna „barva“). To je v rozporu s zbarvení grafu, což je rozdělení vrcholů grafu na daný počet nezávislé sady, bez požadavku, aby tyto nezávislé množiny byly příčné.

Pro ilustraci rozdílu mezi těmito koncepty zvažte fakultu s několika katedrami, kde chce děkan postavit výbor členů fakulty. Někteří členové fakulty jsou však v konfliktu a nebudou sedět ve stejné komisi. Pokud jsou „konfliktní“ vztahy reprezentovány okraji grafu, pak:

  • An nezávislá sada je výbor bez konfliktů.
  • An nezávislé příčné je výbor bez konfliktů s přesně jedním členem z každého oddělení.
  • A zbarvení grafu je rozdělení členů fakulty do výborů bez konfliktů.
  • A silné zbarvení je rozdělení členů fakulty do výborů bez konfliktů a s přesně jedním členem z každé katedry. Tento problém se tedy někdy nazývá šťastný děkan problém.[7]

Reference

  1. ^ Jensen, Tommy R. (1995). Problémy s barvením grafů. Toft, Bjarne. New York: Wiley. ISBN  0-471-02865-7. OCLC  30353850.
  2. ^ Haxell, P. E. (01.11.2004). „On the Strong Chromatic Number“. Kombinatorika, pravděpodobnost a výpočet. 13 (6): 857–865. doi:10.1017 / S0963548304006157. ISSN  0963-5483.
  3. ^ Haxell, P. E. (2008). „Vylepšená hranice silného chromatického čísla“. Journal of Graph Theory. 58 (2): 148–158. doi:10,1002 / jgt.20300. ISSN  1097-0118.
  4. ^ Alon, N. (01.01.1988). „Lineární arboricita grafů“. Israel Journal of Mathematics. 62 (3): 311–325. doi:10.1007 / BF02783300. ISSN  0021-2172.
  5. ^ Alon, Noga (1992). „Silné chromatické číslo grafu“. Náhodné struktury a algoritmy. 3 (1): 1–7. doi:10.1002 / rsa.3240030102.
  6. ^ Fellows, Michael R. (01.05.1990). „Průřezy vrcholů v grafech“. SIAM Journal on Discrete Mathematics. 3 (2): 206–215. doi:10.1137/0403018. ISSN  0895-4801.
  7. ^ Haxell, P. (2011-11-01). „Ve formujících výborech“. Americký matematický měsíčník. 118 (9): 777–788. doi:10,4169 / amer.math.monthly.118.09.777. ISSN  0002-9890.