Podział krawędzi na tęczowe trójkąty

Zastanawiam się, czy następujący problem jest trudny NP.

Wprowadź: prosty wykres i kolorowanie krawędzi ( nie weryfikuje żadnej konkretnej właściwości).$G = (V,E)$$f : E \to \{1,2,3\}$$f$

Pytanie: czy można podzielić na trójkąty , tak aby każdy trójkąt miał jedną krawędź każdego koloru?$E$$|E|/3$

Wiem, że bez kolorów problem „partycjonowania krawędzi” wykresu do , jest NP-trudny (patrz Kompletność NP niektórych problemów z podziałem krawędzi ), ale z kolorami, których nie znam.$K_n$$n \geq 3$

Byłbym również zainteresowany wynikiem podziału krawędzi na tęczę , ze stałą . Oczywiście w tym przypadku problemem staje się:$K_c$$c$

Wprowadź: prosty wykres i kolorowanie krawędzi ( nie weryfikuje żadnej konkretnej właściwości) .$G = (V,E)$$f : E \to \{1,\ldots,c(c-1)/2\}$$f$

Pytanie: czy można podzielić na , tak że każda klika ma jedną krawędź każdego koloru?$E$$|E|/(c(c-1)/2)$ $K_c$$K_c$

za linkiem w pytaniu, a redukcja faktycznie tworzy wykresy, których krawędzie mają naturalne zabarwienie, tak że każdy obecny na wykresie jest „tęczą ” (ma dokładnie jedną krawędź każdego koloru). Innymi słowy, możemy łatwo dostosować redukcję na tym papierze, aby zmniejszała się do twojego problemu zamiast redukować do podziału na problem : po prostu przypisz każdej krawędzi kolor zgodnie z tym naturalnym kolorem, a następnie wykres można podzielić na „rainbow s” wtedy i tylko wtedy, gdy można go w ogóle podzielić na s.$K_n$$K_n$$K_n$$K_n$$K_n$

Podstawową strukturę redukcji tego papieru można osiągnąć za pomocą następujących 3 kroków:

1. Utwórz wiele kopii konkretnego wykresu .$H_{n,p}$
2. Zidentyfikuj niektóre fragmenty niektórych kopii ze sobą (tj. Scal wierzchołki / krawędzie między wieloma różnymi kopiami ).$H_{n,p}$$H_{n,p}$
3. Usuń niektóre wierzchołki / krawędzie z niektórych kopii.

Wykres ma co wierzchołki Zbiór wzdłużnych wektorów modulo , dla którego składniki dodać do mod . Krawędzie łączą co dwa wierzchołki, które różnią się tylko dwoma składnikami z różnicami i w tych dwóch składnikach.$H_{n,p}$$n$$p$$0$$p$$+1$$-1$

Dla tego wykresu proponuję następującą kolorystykę: przypisz kolor każdej krawędzi zgodnie z jej kierunkiem. Jeśli i są sąsiednimi wierzchołkami, a jest wektor z elementów są równe na , jeden element jest równy , a jeden składnik równy . Innymi słowy, dla każdej krawędzi istnieją opcje, dla których składowe są niezerowe. Jeśli przypiszemy unikalny kolor do każdej z tych opcji, będziemy mieli kolor wszystkich krawędzi, tak aby każda krawędź w tym samym kierunku miała ten sam kolor. Bardzo łatwo jest sprawdzić, czy w nie ma dwóch krawędzi$x$$y$$x-y$$n-2$$0$$1$$-1$$(x, y)$${n \choose 2}$$x-y$$K_n$w są w tym samym kierunku. Dlatego każdy w jest tęczą pod tym zabarwieniem.$H_{n,p}$$K_n$$H_{n,p}$$K_n$

Kiedy podążamy za redukcją, używamy tego kolorowania dla każdej kopii . Dlatego na końcu kroku 1 na powyższej liście każdy na wykresie jest tęczą .$H_{n,p}$$K_n$$K_n$

W kroku 2 powyższej listy identyfikujemy niektóre wierzchołki / krawędzie. W szczególności w redukcji zawsze identyfikujemy z innym . Ale w tej sytuacji (gdzie wszystkie pochodzą z kopii ), każdy jest albo tłumaczeniem „standardowego ”, które gazeta nazywa albo tłumaczeniem . Dlatego identyfikujemy albo dwa równoległe albo dwa które są „ ”. W obu przypadkach krawędzie są identyfikowane na dwóch$K_n$$K_n$$K_n$$H_{n,p}$$K_n$$K_n$$K$$-K$$K_n$$K_n$$K_n$s są równoległe i dlatego są tego samego koloru. Na przykład patrz rysunek 2 w artykule; zidentyfikowane krawędzie są zawsze równoległe. Zatem, ponieważ nigdy nie próbujemy zidentyfikować dwóch krawędzi o różnych kolorach, zabarwienie na końcu kroku 1 na powyższej liście można naturalnie rozszerzyć na zabarwienie na końcu kroku 2. Zidentyfikowanie niektórych wierzchołków / krawędzi nie tworzy razem wszelkie nowe , więc na końcu tego kroku nadal jest tak, że każdy jest tęczą .$K_n$$K_n$$K_n$

Wreszcie w kroku 3 usuwamy niektóre wierzchołki / krawędzie, które również nie tworzą nowych . Mamy zatem naszą pożądaną właściwość: pod podanym każde na wykresie wygenerowanym przez tę redukcję jest tęczą .$K_n$$K_n$$K_n$