Dureté d'approximation du nombre chromatique fractionnaire sur les graphiques de degrés bornés

Réponses:

11

Oui.

Si j'ai bien compris, la preuve du théorème 1.6 de Khot (2001) établit qu'il est difficile de faire la distinction entre les deux cas suivants, même si nous nous concentrons sur des graphiques à degrés bornés de degré suffisamment élevé:

  1. Il y a une couleur .k
  2. Le rapport du nombre de sommets à la taille maximale d'un ensemble indépendant est d'au moins .kJournal(k)/25

Du point de vue du nombre chromatique fractionnaire, ces deux cas sont:

  1. Le nombre chromatique fractionnaire est au plus .k
  2. Le nombre chromatique fractionnaire est d'au moins .kJournal(k)/25

Maintenant, nous devons nous rappeler que nous avons besoin de degrés suffisamment élevés (en fonction de ). Mais pour autant que je puisse voir, la preuve a, par exemple, le corollaire pratique suivant qui pourrait déjà être suffisant pour vos besoins:k

  • Étant donné toute constante , il existe des constantes Δ et c telles que le problème suivant en NP-dur: étant donné un graphique G de degré maximal Δ , décidez si le nombre chromatique fractionnaire de G est au plus c ou au moins α c .αΔcgΔgcαc

Bien sûr, cela implique déjà qu'il n'y a pas de PTAS, sauf si P = NP.

Jukka Suomela
la source
Le dernier corollaire a sûrement d'autres modificateurs sur les constantes, sinon c'est très bien connu pour les petites valeurs de , c 1 et c 2 ...Δc1c2
Andrew D. King
@ AndrewD.King: D'accord, vous pouvez rendre n'importe laquelle d'entre elles arbitrairement grande, etc. Mais peut-être pourriez-vous poster une réponse qui montre que la version simple du corollaire peut être dérivée en utilisant des techniques plus anciennes et plus faciles - je pense que ce suffisant pour répondre à la question d'OP?
Jukka Suomela
kΔc1c2kc1<c2
@ AndrewD.King: Oui, je vais modifier la réponse; j'espère que cela aura plus de sens de cette façon. :)
Jukka Suomela