Czy kolory wierzchołków - w pewnym sensie - są kolorami krawędzi?

Wiadomo, że barwniki krawędzi grafu są barwniki wierzchołku specjalnej wykresu, a mianowicie na wykresie linia L ( G ) o G .$G$ $L(G)$$G$

Czy istnieje operator wykresu taki, że zabarwienie wierzchołków wykresu G jest zabarwieniem krawędzi wykresu Φ ( G ) ? Interesuje mnie taki operator wykresu, który można konstruować w czasie wielomianowym, tj. Wykres Φ ( G ) można uzyskać z G w czasie wielomianowym.$\Phi$$G$ $\Phi(G)$$\Phi(G)$$G$

Uwaga : Podobne pytanie można zadać dla stabilnych zestawów i dopasowań. Dopasowanie w jest stabilnym zestawem w L ( G ) . Czy istnieje operator grafu Ψ taki, że zestawy stabilne w G są dopasowaniami w Ψ ( G ) ? Od trwałego zestawu jest N P -Complete i pasujące do nich należy do P , na przykład operator wykres Ψ (jeśli istnieje), nie może być wykonane w czasie wielomianowym, przy założeniu, że N P ≠ P . $G$$L(G)$$\Psi$$G$$\Psi(G)$$\mathsf{ NP}$$\mathsf{P}$$\Psi$$\mathsf{NP}\not=\mathsf{P}$

EDYCJA: Zainspirowany odpowiedzią @ usul oraz komentarzami @ Okamoto i @ King, znalazłem słabszą formę dla mojego problemu: Kolorowanie wierzchołków wykresu to zabarwienie krawędzi hipergrafu Φ ( G ) zdefiniowane w następujący sposób. Wierzchołek zestaw cp ( G ) jest ten sam zestaw wierzchołek G . Dla każdego wierzchołka v o G zamknięta sąsiedztwo N G [ V ] = N G ( V ) ∪ { v } jest krawędź hipergraf cp ( $G$ $\Phi(G)$$\Phi(G)$$G$$v$$G$$N_G[v]= N_G(v) \cup\{v\}$ . Zatem G jest wykresem liniowym hipergrafu Φ ( G ), a zatem zabarwienie wierzchołków G jest zabarwieniem krawędzi Φ ( G ) .$\Phi(G)$$G$$\Phi(G)$$G$$\Phi(G)$

Ponownie jestem wdzięczny za wszystkie odpowiedzi i komentarze wskazujące, że przy założeniu lub bez niego operator, którego szukam, nie może istnieć. Byłoby miło, gdybym mógł zaakceptować wszystkie odpowiedzi!$\mathsf{NP}\not=\mathsf{P}$

Myślę, że przez analogię z wykresem liniowym pytasz:

Czy dla każdego nieukierowanego wykresu istnieje nieukierowany wykres G ′ = ( V ′ , E ′ ), taki że każdy wierzchołek v ∈ V odpowiada krawędzi ( v 1 , v 2 ) ∈ E ′ i krawędzie odpowiadające u ∈ V i v ∈ V dzielą co najmniej jeden punkt końcowy wtedy i tylko wtedy, gdy ( u , v $G = (V,E)$$G' = (V',E')$$v \in V$$(v_1,v_2) \in E'$$u \in V$$v \in V$ ?$(u,v) \in E$

Odpowiedź może brzmieć „ nie” . Rozważmy drzewo z czterema wierzchołkami z rdzeniem v mającym troje potomków x , y , z . W G ′ musimy mieć cztery krawędzie: ( v 1 , v 2 ) , ( x 1 , x 2 ) , ( y 1 , y 2 ) , ( z 1 , z 2 ) . Ponadto musi być tak, że albo $G$$v$$x,y,z$$G'$$(v_1,v_2),(x_1,x_2),(y_1,y_2),(z_1,z_2)$ lub V 2 stanowi punkt końcowy każdego z innych trzech krawędzi (tj, | { v 1 , V, 2 } ∩ { x 1 , x 2 } | ≥ 1 , itd.) Oznacza to jednak, że co najmniej dwie z pozostałych trzech krawędzi muszą mieć wspólny punkt końcowy, co narusza nasze wymagania, ponieważ żadne z dwóch x , y , z nie sąsiadują na oryginalnym wykresie.$v_1$$v_2$$\left| \{v_1,v_2\} \cap \{x_1,x_2\} \right| \geq 1$$x,y,z$

Myślę, że ten sam wykres da również kontrprzykład dla pasującego pytania.

Pytanie zawiera pewną dwuznaczność w tym, co rozumiesz przez „zabarwienie wierzchołków wykresu G to zabarwienie krawędzi wykresu H ”, ale trudno jest zbudować wykres, którego krawędziowa liczba chromatyczna jest równa (wierzchołkowej) liczbie chromatycznej dany wykres. Formalnie następujący problem relacji jest trudny w NP.

Reprezentujący numer chromatycznej jako krawędź numer chromatycznej
Instancji : wykres G .
Roztwór : Wykres H tak, że krawędź liczba chromatyczna χ '( H ) w H wynosi chromatycznej numer Ď ( G ) o G .

Wynika to z faktu, że twierdzenie Vizinga daje (trywialny) skuteczny algorytm, który aproksymuje krawędź liczby chromatycznej z błędem addytywnym wynoszącym 1, podczas gdy liczba chromatyczna jest trudna do przybliżenia nawet w różnych sensach. Na przykład Khanna, Linial i Safra [KLS00] pokazali, że następujący problem jest NP-zupełny (a później Guruswami i Khanna [GK04] podali znacznie prostszy dowód):

3-colorable porównaniu non-4-colorable
wystąpienia : Wykres G .
Tak, obietnica : G można pokolorować w 3 kolorach.
Bez obietnicy : G nie jest 4-kolorowe.

Ten wynik jest wystarczający, aby udowodnić twardość NP, którą twierdziłem na początku. Dowód pozostaje jako ćwiczenie, ale oto wskazówka:

Ćwiczenia . Udowodnij, że wyżej wspomniany problem „Reprezentowanie liczby chromatycznej jako krawędziowej liczby chromatycznej” jest trudny do NP przy funkcjonalnej redukcji w czasie wielomianowym przez zmniejszenie do niego „3-kolorowalnych kontra nie-4-barwnych”. Oznacza to, że skonstruuj dwie funkcje czasu wielomianowego f (który odwzorowuje wykres na wykres) i g (który odwzorowuje wykres na bit) tak, aby

• Jeśli G jest trójkolorowym wykresem, a H jest takim wykresem, że χ ( f ( G )) = χ '( H ), to g ( H ) = 1.
• Jeśli G jest grafem bez 4 kolorów, a H jest takim wykresem, że χ ( f ( G )) = χ '( H ), to g ( H ) = 0.

Bibliografia

[GK04] Venkatesan Guruswami i Sanjeev Khanna. Na twardości 4-kolorowania 3-kolorowy graf. SIAM Journal on Discrete Mathematics , 18 (1): 30–40, 2004. DOI: 10.1137 / S0895480100376794 .

[KLS00] Sanjeev Khanna, Nathan Linial i Shmuel Safra. O twardości zbliżenia liczby chromatycznej. Combinatorica , 20 (3): 393–415, marzec 2000 r. DOI: 10.1007 / s004930070013 .

$\Phi$$G$$G'$$G = L(G')$$G$$\Phi$$L^{-1}$$\Phi(G)=G'$$G$$\Phi(G)$