Problemy z kolorowaniem wykresów są już wystarczająco trudne dla większości ludzi . Mimo to będę musiał być trudny i zapytać o barwienie metodą hypergraph.
Pytanie.
Jakie są skuteczne algorytmy do znalezienia w przybliżeniu optymalnego zabarwienia krawędzi dla hipergraphów jednolitych k?
Detale ---
Hypergraph k-uniform to taki, w którym każda krawędź zawiera dokładnie k wierzchołków; zwykłym przypadkiem prostego wykresu jest k = 2. Mówiąc dokładniej, interesują mnie oznaczone hipergrrafy k-uniform, w których dwie krawędzie mogą mieć ten sam zestaw wierzchołków; ale zadowolę się czymś na k-regularnych hipergraphach z krawędziami przecinającymi się nie więcej niż k-1 wierzchołkami.
Kolorowanie krawędzi hypergraphs to takie, w którym krawędzie tego samego koloru nie przecinają się, jak w przypadku wykresów. Indeks chromatyczny χ '(H) jest, jak zwykle, minimalną wymaganą liczbą kolorów.
Chciałbym wyniki na deterministycznych lub losowych algorytmach wielomianu czasu.
Szukam najlepiej znanego współczynnika aproksymacji / luki dodatków między tym, co można skutecznie znaleźć, a rzeczywistym indeksem chromatycznym χ '(H) --- lub, w związku z tym, najlepiej osiągalnym wynikiem pod względem parametrów takich jak maksymalny stopień wierzchołka ((H), rozmiar hipergraphu itp.
Edit: prośba o uwagach Suresh za około felg bliźniaczych hipergraf Poniżej Należy zauważyć, że problem ten jest równoznaczny z problemem znalezienia silnego wierzchołek kolorowania z k-regularny hipergraf to znaczy, gdzie każdy wierzchołek należy do k wyraźne krawędzie, [ale krawędzie może teraz zawierać różną liczbę wierzchołków] i chcemy kolorowania wierzchołków tak, aby dowolne dwa sąsiednie wierzchołki miały różne kolory. To przeformułowanie również nie wydaje się mieć oczywistego rozwiązania.
Uwagi
W przypadku grafów Twierdzenie Vizinga nie tylko gwarantuje, że liczba krawędziowo-chromatyczna dla wykresu G wynosi albo Δ (G) lub Δ (G) +1, standardowe dowody tego dają również skuteczny algorytm do znalezienia Δ (G ) + Kolorowanie 1-krawędziowe. Ten wynik byłby dla mnie wystarczająco dobry, gdybym był zainteresowany sprawą k = 2; jednak jestem szczególnie zainteresowany dowolnością k> 2.
Wydaje się, że nie ma żadnych dobrze znanych wyników dotyczących granic kolorowania krawędzi hipergrafu, chyba że dodasz ograniczenia, takie jak każda krawędź przecinająca się co najwyżej t wierzchołków. Ale nie potrzebuję granic samego χ '(H); tylko algorytm, który znajdzie „wystarczająco dobre” zabarwienie krawędzi. [Nie chcę również nakładać żadnych ograniczeń na moje hipergrrafy, z wyjątkiem tego, że są k-jednolite, i być może ogranicza się do maksymalnego stopnia wierzchołka, np.) (H) ≤ f (k) dla niektórych f ∈ ω (1) .]
[ Dodatek. Zadałem teraz pokrewne pytanie na MathOverlow dotyczące granic liczby chromatycznej, konstruktywnych lub innych.]