Les colorations des sommets - dans un sens - sont-elles des colorations des bords?

Nous savons que des colorants bord de un graphe sont des colorants sommets d'un graphe spécial, à savoir du graphique de la ligne de . $G$ $L(G)$ $G$

Existe-t-il un opérateur de graphe tel que les colorations des sommets d'un graphe sont des colorations de bord du graphe ? Je m'intéresse à un tel opérateur de graphe qui peut être construit en temps polynomial, c'est-à-dire que le graphe peut être obtenu à partir de en temps polynomial. $\Phi$ $G$ $\Phi(G)$ $\Phi(G)$ $G$

Remarque : Une question similaire peut être posée pour les ensembles et les correspondances stables. Une correspondance en $G$ est un ensemble stable en $L(G)$ . Existe-t-il un opérateur graphique $\Psi$ tel que les ensembles stables dans $G$ sont des correspondances dans $\Psi(G)$ ? Puisque STABLE SET est $\mathsf{ NP}$ -complete et MATCHING appartient à $\mathsf{P}$ , un tel opérateur de graphique $\Psi$ (s'il existe) ne peut pas être construit en temps polynomial, en supposant que $\mathsf{NP}\not=\mathsf{P}$ .

EDIT: Inspiré par la réponse de @ usul et les commentaires de @ Okamoto et @ King, j'ai trouvé une forme plus faible pour mon problème: les colorations de d'un graphique $G$ sont les couleurs de bord d'un hypergraphe $\Phi(G)$ défini comme suit. L'ensemble des sommets de $\Phi(G)$ est le même ensemble de sommets de $G$ . Pour chaque sommet $v$ de $G$ , le voisinage fermé $N_G[v]= N_G(v) \cup\{v\}$ est un bord de l'hypergraphe $\Phi(G)$ . Alors $G$ est le graphique linéaire de l'hypergraphe $\Phi(G)$ et donc les colorations des sommets de $G$ sont les colorations des bords de $\Phi(G)$ .

Encore une fois, je suis reconnaissant pour toutes les réponses et commentaires montrant que, avec ou sans supposer , l'opérateur que je recherche ne peut pas exister. Ce serait bien si je pouvais accepter toutes les réponses! $\mathsf{NP}\not=\mathsf{P}$

graph-theory graph-algorithms user13136
la source

Merci à tous pour vos aimables commentaires (et votre patience!) Et vos réponses utiles. J'ai besoin de temps pour lire, pour réfléchir et je pourrais peut-être revenir avec de nouveaux yeux.

user13136

Je suis tombé sur le problème très intéressant suivant posé par Nishizeki et Zhou en 1998 qui est en quelque sorte lié à votre question et à votre deuxième commentaire à @TsuyoshiIto: le problème de coloration des sommets peut-il être "simplement" réduit au problème de coloration des bords? (...) Étant donné que les deux problèmes sont NP-complets, l'un ou l'autre peut être réduit à l'autre de manière plausible grâce au 3-SAT, en raison de la théorie de la complétude NP. Ainsi le problème ouvert demande, ... (voir ici )

vb le

@vble: merci! J'avoue que je voulais "trop". Un tel opérateur résoudrait le problème de Nishizeki et Zhou.

user13136

Réponses:

Par analogie avec le graphique linéaire , je pense que vous posez les questions suivantes:

Pour chaque graphe non orienté , existe-t-il un graphe non orienté tel que chaque sommet correspond à une arête et les arêtes correspondant à et partagent au moins un point d'extrémité si et seulement si ? $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$

On peut voir que la réponse est non . Considérons l'arbre à quatre sommets dont la racine trois enfants . En , nous devons avoir quatre arêtes: . De plus, il doit être le cas que ou soit un point d'extrémité de chacun des trois autres bords ( c'est-à - dire , , etc). Mais cela signifie qu'au moins deux des trois autres arêtes doivent partager un point de terminaison commun, ce qui viole nos exigences car aucun de n'est adjacent dans le graphique d'origine. $G$ $v$ $x,y,z$ $G'$ $(v_1,v_2),(x_1,x_2),(y_1,y_2),(z_1,z_2)$ $v_1$ $v_2$ $\left| \{v_1,v_2\} \cap \{x_1,x_2\} \right| \geq 1$ $x,y,z$

Je pense que le même graphique vous donnera également un contre-exemple pour la question correspondante.

usul
la source

Bon point! En fait, j'avais les mêmes pensées. Mais peut-être existe-t-il une autre façon de définir ? Ou comment prouver formellement qu'un tel opérateur n'existe pas?

G^{'}

$G'$

Φ

$\Phi$

user13136

@ user13136, hmm, il y a peut-être un moyen créatif de contourner cela, mais vous devrez reformuler votre question (je pense que mon contre-exemple est une preuve formelle de la question telle que formulée dans l'encadré). Intuitivement, je pense que le problème est que lorsque nous allons dans la direction du graphique linéaire, nous prenons un bord (qui ne peut être connecté qu'à deux sommets) et le transformons en un sommet (qui peut être connecté à un nombre quelconque d'arêtes) - facile . L'inverse est opposé et plus dur.

usul

En ajoutant simplement à la réponse d'Usul, la réponse courte est non, car les correspondances ont des propriétés structurelles qui ne sont pas nécessairement présentes dans les ensembles stables. Par exemple, chaque graphique linéaire est également quasi linéaire et sans griffes; cela limite vraiment la profondeur des colorations des bords par rapport aux colorations des sommets.

Andrew

La question contient une certaine ambiguïté dans ce que vous entendez par «les colorations des sommets d'un graphique G sont les colorations des bords d'un graphique H », mais il est difficile de construire un graphique dont le nombre chromatique des bords est égal au nombre chromatique (vertex) de un graphique donné. Formellement, le problème de relation suivant est NP-difficile.

La représentation chromatique en tant que nombre chromatique de bord
instance : Un graphe G .
Solution : Un graphe H de telle sorte que le bord de χ chromatique '( H ) de H est égal au nombre de χ chromatique ( G ) de G .

C'est parce que le théorème de Vizing donne un algorithme efficace (trivial) qui se rapproche du nombre chromatique de front dans une erreur additive de 1 alors que le nombre chromatique est difficile même à approximer dans divers sens. Par exemple, Khanna, Linial et Safra [KLS00] ont montré que le problème suivant est NP-complet (et plus tard Guruswami et Khanna [GK04] ont donné une preuve beaucoup plus simple):

3-colorable par rapport aux non-4-colorable
instance : Un graphe G .
Oui-promesse : G est tricolore.
Pas de promesse : G n'est pas 4 couleurs.

Ce résultat est suffisant pour prouver la dureté NP que j'ai revendiquée au début. Une preuve est laissée en exercice, mais voici un indice:

Faites de l'exercice . Démontrer que le problème susmentionné «Représenter le nombre chromatique comme nombre chromatique de bord» est NP-dur sous la réductibilité fonctionnelle en temps polynomial en réduisant «3-colorable contre non-4-colorable». Autrement dit, construisez deux fonctions polynomiales f (qui mappent un graphe sur un graphe) et g (qui mappe un graphe sur un bit) de telle sorte que

Si G est un graphique tricolore et H est un graphique tel que χ ( f ( G )) = χ '( H ), alors g ( H ) = 1.

Si G est un graphe non colorable en 4 et H est un graphe tel que χ ( f ( G )) = χ '( H ), alors g ( H ) = 0.

Les références

[GK04] Venkatesan Guruswami et Sanjeev Khanna. Sur la dureté de la coloration 4, un graphique 3 couleurs. SIAM Journal on Discrete Mathematics , 18 (1): 30–40, 2004. DOI: 10.1137 / S0895480100376794 .

[KLS00] Sanjeev Khanna, Nathan Linial et Shmuel Safra. Sur la dureté d'approximation du nombre chromatique. Combinatorica , 20 (3): 393–415, mars 2000. DOI: 10.1007 / s004930070013 .

Tsuyoshi Ito
la source

Merci de votre réponse! Je suis un peu imprécis en formulant «les colorations des sommets d'un graphe

sont les colorations des bords d'un graphe

». Ce que je veux dire, c'est un opérateur

comme l'opérateur de graphique linéaire

, mais des colorations des sommets aux colorations des bords. C'est en quelque sorte plus que

G

$G$

H

$H$

Φ

$\Phi$

L

$L$

χ (G) = χ^{'} (H)

$\chi(G) = \chi'(H)$

user13136

Étant donné que VERTEX COLORING et EDGE COLORING sont tous deux

-complets, nous pouvons construire, par définition,

partir de

en temps polynomial de telle sorte que

ssi

.Mais une telle construction n'a pas besoin réaliser la propriété d'un opérateur

je recherche. Il réduit uniquement les colorations des sommets aux couleurs des bords.

N P

$\mathsf{NP}$

H

$H$

G

$G$

χ (G) \leq k

$\chi(G) \le k$

χ^{'} (H) \leq k^{'}

$\chi'(H) \le k'$

Φ

$\Phi$

user13136

@ user13136: Si une exigence plus faible est impossible à satisfaire, l'exigence plus forte est évidemment également impossible. C'est logique. Vous devez comprendre que votre exemple de graphique planaire n'est pas un contre-exemple à cela. Décider de la 3-colorabilité d'un graphique plan donné n'est pas une exigence plus faible que de décider de la 4-colorabilité d'un graphique plan donné; ce ne sont que des exigences différentes. D'un autre côté, j'ai déjà montré que ce que vous voulez est impossible à moins que P = NP, point. Mais si vous avez du mal à comprendre cela, je ne pense pas que je puisse faire quoi que ce soit pour vous aider à comprendre.

Tsuyoshi Ito

Si je comprends bien la question, une telle carte

n'existe pas. Nous n'avons pas besoin de faire référence à l'exhaustivité de NP. Considérons simplement

et supposons

tel

existe. Puisque

est bicolore,

devrait être bicolore. Cela signifie que le degré maximum de

est au maximum de deux. Puisque

a quatre arêtes, nous pouvons passer en revue tous les candidats pour

Φ

$\Phi$

G = K_{1, 3}

$G=K_{1,3}$

Φ (G)

$\Phi(G)$

G

$G$

Φ (G)

$\Phi(G)$

Φ (G)

$\Phi(G)$

Φ (G)

$\Phi(G)$

Φ (G)

$\Phi(G)$ (sept candidats jusqu'à l'isomorphisme), et nous constaterons que la famille des colorations des bords de

et la famille des colorations des sommets de

sont différentes. Une contradiction.

Φ (G)

$\Phi(G)$

G

$G$

Yoshio Okamoto

@ user13136: Il m'est venu à l'esprit que vous étiez peut-être confus parce que je n'ai écrit qu'une idée de preuve et que j'ai omis la preuve réelle. J'ai révisé la réponse pour qu'il soit clair que j'ai omis la preuve réelle et ajouté quelques indices pour la preuve. Si cela ne fonctionne toujours pas pour vous, alors j'abandonnerai.

Tsuyoshi Ito

(Ceci est un ajout à la réponse d'Usul et au commentaire de YoshioOkamoto, plutôt qu'une réponse.) On peut voir que votre opération n'existe que pour les graphiques pour lesquels il existe un graphique avec , c'est-à-dire est un graphe linéaire (vérifiable en polytime). Dans ce cas, est "l'opérateur de graphique en courbes inverses" , c'est-à-dire , et les colorations des sommets de sont des colorations des bords de $\Phi$ $G$ $G'$ $G = L(G')$ $G$ $\Phi$ $L^{-1}$ $\Phi(G)=G'$ $G$ . $\Phi(G)$

En théorie
la source