Seznam zbarvení hran - List edge-coloring

v matematika, seznam zbarvení hran je typ zbarvení grafu který kombinuje seznam zbarvení a zbarvení hran Instance problému se zbarvením okraje seznamu se skládá z grafu a seznamu povolených barev pro každou hranu. Barvení okraje seznamu je výběr barvy pro každou hranu ze seznamu povolených barev; zbarvení je správné, pokud žádné dva sousední okraje nedostanou stejnou barvu.

Graf G je k-strana-volitelná pokud každá instance seznamu zbarvení hran, která má G jako jeho podkladový graf a který poskytuje alespoň k povolené barvy pro každou hranu G má správné zbarvení možnost výběru hranynebo seznam barevnosti hran, chromatické číslo hrany seznamunebo seznam chromatický index, ch '(G) grafu G je nejmenší číslo k takhle G je k-strana-volitelná. Předpokládá se, že se vždy rovná chromatický index.

Vlastnosti

Některé vlastnosti ch ′ (G):

  1. ch ′ (G) <2 χ ′ (G).
  2. ch '(K.n,n) = n. To je Dinitzova domněnka, prokázáno Galvin (1995).
  3. ch ′ (G) <(1 + o (1)) χ ′ (G), tj. chromatický index seznamu a chromatický index se asymptoticky shodují (Kahn 2000 ).

Zde χ ′ (G) je chromatický index z G; a K.n,n, kompletní bipartitní graf se stejnými partitové sady.

Seznam zbarvení dohad

Nejznámějším otevřeným problémem zbarvení okrajů seznamu je pravděpodobně seznam zbarvení dohad.

ch ′ (G) = χ ′ (G).

Tato domněnka má fuzzy původ; Jensen & Toft (1995) přehled jeho historie. Dinitzova domněnka, prokázaná Galvin (1995), je zvláštní případ domněnky o zbarvení seznamu pro kompletní bipartitní grafy K.n,n.

Reference

  • Galvin, Fred (1995), „Seznam chromatických indexů bipartitního multigrafu“, Journal of Combinatorial Theory, Řada B, 63: 153–158, doi:10.1006 / jctb.1995.1011.
  • Jensen, Tommy R .; Toft, Bjarne (1995), „12.20 List-Edge-Chromatic Numbers“, Problémy s barvením grafů, New York: Wiley-Interscience, s. 201–202, ISBN  0-471-02865-7.
  • Kahn, Jeff (2000), „Asymptotika seznamu chromatického indexu pro multigrafy“, Náhodné struktury a algoritmy, 17 (2): 117–156, doi:10.1002 / 1098-2418 (200009) 17: 2 <117 :: AID-RSA3> 3.0.CO; 2-9