Une coloration plane incorrecte avec une taille de composant monochromatique

11

Relâchons un peu la coloration, c'est-à-dire que nous permettons à un petit nombre de sommets adjacents de se voir attribuer la même couleur. Un composant monochromatique est défini comme étant un composant connecté dans le sous-graphique induit par l'ensemble de sommets qui reçoivent la même couleur, et la question est de demander le nombre minimum de couleurs nécessaires pour colorer un graphique de telle sorte que le plus grand composant monochromatique ait taille maximum . CλC
La coloration traditionnelle peut être considérée comme une coloration dans ce paramètre. Par conséquent, trouver le nombre minimum de est NP-difficile pour le graphe planaire en général. λ[λ,1]λ

Ma question est la suivante qu'en est-il de la coloration des graphes planaires , ou plus généralement, de la coloration pour ?[λ,2]C 2[λ,C]C2

Cela peut être considéré comme un double problème de ce qui est étudié par Edwards et Farr , où est fixe, et on est demandé de trouver la taille minimale de .CλC

Yixin Cao
la source

Réponses:

3

L'appariement parfait bicolore dans les graphiques planaires cubiques est très similaire à votre problème qui a été déclaré NP-complet par Schaefer dans son célèbre papier de théorème de dichotomie, bien qu'il n'ait pas donné la preuve pour les graphiques planaires cubiques. Le problème demande l'existence de deux colorations de graphes planaires cubiques telles que chaque sommet ait exactement un voisin de la même couleur que lui.

EDIT: La coloration défectueuse est la version de décision de votre problème. Un graphique est (k, d) -colorable si l'on peut colorer les sommets avec k couleurs de sorte qu'aucun sommet ne soit adjacent à plus de d sommets de sa même couleur. Le problème de décision (2,1) - coloration avec défauts, qui équivaut à votre problème d'optimisation, s'est avéré être NP-complet même pour les graphes planaires .

Mohammad Al-Turkistany
la source
Qu'est-ce qu'une réduction de la "correspondance parfaite bicolore dans les graphiques planaires cubiques" au problème de Yixin?
La correspondance parfaite bicolore est un cas spécial où la taille maximale des composants connectés est exactement égale à C.
Mohammad Al-Turkistany
Merci pour votre réponse, mais je ne peux pas être d'accord avec vous. Comme dans le problème "Correspondance parfaite bicolore dans les graphes planaires cubiques", CHAQUE composant doit être exactement 2. Mais ma question semble plus facile.
Yixin Cao
Oui, j'ai raté cette différence.
Mohammad Al-Turkistany