Wypisz kolorowanie krawędzi

W matematyce kolorowanie krawędzi listy to rodzaj kolorowania wykresów , który łączy kolorowanie list i kolorowanie krawędzi . Przykład problemu z kolorowaniem krawędzi listy składa się z wykresu wraz z listą dozwolonych kolorów dla każdej krawędzi. Lista kolorowania krawędzi to wybór koloru dla każdej krawędzi z listy dozwolonych kolorów; kolorowanie jest właściwe, jeśli żadne dwie sąsiednie krawędzie nie otrzymają tego samego koloru.

Graf G jest k -krawędziowy do wyboru , jeśli każdy przypadek listowego kolorowania krawędzi, dla którego G jest grafem bazowym i który zapewnia co najmniej k dozwolonych kolorów dla każdej krawędzi G , ma odpowiednie zabarwienie. Możliwość wyboru krawędzi lub możliwość kolorowania krawędzi listy , liczba chromatyczna krawędzi listy lub indeks chromatyczny listy , ch′( G ) grafu G jest najmniejszą liczbą k taką, że G jest k -krawędź do wyboru. Przypuszcza się, że zawsze jest równy indeksowi chromatycznemu .

Nieruchomości

Niektóre własności ch′( G ):

1. ch′( sol ) < 2 χ′( sol ).
2. ch′(K _{n , n} ) = n . Jest to hipoteza Dinitza , udowodniona przez Galvina (1995) .
3. ch′( G ) < (1 + o(1))χ′( G ), tj. indeks chromatyczny listy i indeks chromatyczny zgadzają się asymptotycznie ( Kahn 2000 ).

Tutaj χ′( G ) jest indeksem chromatycznym G ; i K _{n , n} , pełny graf dwudzielny z równymi zbiorami cząstkowymi .

Wypisz przypuszczenia dotyczące kolorowania

Najbardziej znanym otwartym problemem dotyczącym kolorowania krawędzi listy jest prawdopodobnie hipoteza dotycząca kolorowania list .

ch′( sol ) = χ′( sol ).

To przypuszczenie ma niejasne pochodzenie; Jensen i Toft (1995) opisują jego historię. Hipoteza Dinitza, udowodniona przez Galvina (1995) , jest szczególnym przypadkiem hipotezy kolorowania listy dla pełnych grafów dwudzielnych K _{n , n} .

• Galvin, Fred (1995), „Lista chromatyczna indeks dwudzielnego multigrafu”, Journal of Combinatorial Theory , Seria B, 63 : 153–158, doi : 10.1006/jctb.1995.1011 .
•   Jensen, Tommy R.; Toft, Bjarne (1995), „12,20 List-Edge-Chromatic Numbers”, Graph Coloring Problems , Nowy Jork: Wiley-Interscience, s. 201–202, ISBN 0-471-02865-7 .
• Kahn, Jeff (2000), „Asymptotyka indeksu chromatycznego listy dla multigrafów”, Random Structures & Algorithms , 17 (2): 117–156, doi : 10,1002/1098-2418 (200009) 17: 2 <117 :: AID -RSA3>3.0.CO;2-9