Raisons pour lesquelles un graphique peut ne pas être

En raisonnant un peu sur cette question , j'ai essayé d'identifier toutes les différentes raisons pour lesquelles un graphe peut ne pas être k colorable. Ce sont les 2 seules raisons que j'ai pu identifier jusqu'à présent:$G = (V_G,E_G)$$k$

1. contient une clique de taille k + 1 . Telle est la raison évidente.$G$$k+1$

2. Il existe un sous-graphe de G tel que les deux énoncés suivants sont vrais:$H = (V_H, E_H)$$G$

   • n'est pas k - 1 colorable.$H$$k-1$
   • . Enautres termesil existe un nœud x dans G mais pas en H ,telle sorte que x est connecté à chaque nœud H .$\exists x \in V_G - V_H\ \forall y \in V_H\ \{x,y\} \in E_G$$x$$G$$H$$x$$H$

Nous pouvons voir les 2 raisons ci-dessus comme des règles. En les appliquant récursivement, les 2 seules façons de construire un graphe colorable non qui ne contient pas de clique k + 1 sont:$k$$k+1$

1. Commencez par un cycle de longueur paire (qui est colorable), puis appliquez la règle 2 pour k - 1 fois. Notez qu'une arête n'est pas considérée comme un cycle de longueur 2 (sinon ce processus aurait pour effet de construire une clique k + 1 ).$2$$k-1$$2$$k+1$
2. Commencez par un cycle de longueur impaire (qui est colorable), puis appliquez la règle 2 pour k - 2 fois. La durée du cycle de départ doit être supérieure à 3 (sinon ce processus aurait pour effet de construire une clique k + 1 ).$3$$k-2$$3$$k+1$

Question

Y a-t-il une autre raison, autre que celles 2 ci-dessus, qui rend un graphique non colorable?$k$

$\ $
Mise à jour 30/11/2012

Plus précisément, j'ai besoin d'un théorème de la forme:

Un graphe a un nombre chromatique χ ( G ) = k + 1 si et seulement si ...$G$$\chi(G) = k + 1$

Le calcul de Hajós , souligné par Yuval Filmus dans sa réponse, est un parfait exemple de ce que je recherche, car un graphique a un nombre chromatique χ ( G ) = k + 1 si et seulement s'il peut être dérivé de l'axiome K k + 1 en appliquant à plusieurs reprises les 2 règles d'inférence du calcul. Le nombre de Hajós h ( G ) est alors le nombre minimum d'étapes nécessaires pour dériver G (c'est-à-dire qu'il est la longueur de la preuve la plus courte).$G$$\chi(G) = k + 1$$K_{k+1}$$h(G)$$G$

Il est très intéressant que:

• La question de savoir s'il existe un graphe dont h ( G ) est exponentiel dans la taille de G est toujours ouverte.$G$$h(G)$$G$
• Si tel n'existe pas, alors N P = c o N P .$G$$NP = coNP$

Vous devriez vérifier le calcul Hajós . Hajós a montré que chaque graphique avec un nombre chromatique au moins a un sous - graphique qui a une "raison" d'exiger k couleurs. La raison en question est un système d'épreuve pour exiger k couleurs. Le seul axiome est K k , et il y a deux règles d'inférence. Voir aussi cet article de Pitassi et Urquhart sur l'efficacité de ce système de preuve.$k$$k$$k$$K_k$

Une réponse partielle, en ce sens que je ne connais pas une belle "raison" qui puisse être généralisée, mais le graphique suivant (sans vergogne entaillé d' ici ):

N'est pas 3-colorable, mais est évidemment 4-colorable (étant planaire), et il ne contient pas de , ni aucun cycle avec un sommet supplémentaire connecté à tous les sommets du cycle (sauf s'il me manque quelque chose, mais les seuls sommets connecté à un sommet et son voisin sont dans les 3 cycles). Pour aller plus loin, vous pouvez appliquer une version de la règle 2 pour obtenir un graphique du nombre chromatique 5.$K_{4}$

Je soupçonne que pour un genre donné, il y a un graphique d'un certain nombre chromatique minimum (voir la conjecture de Heawood ) qui ne suit pas les règles 1 ou 2. Bien sûr, je n'ai aucune preuve autre que l'intuition.

Lovasz a trouvé des obstructions topologiques pour la k-colorabilité et a utilisé sa théorie pour résoudre la conjecture de Knaser. Son théorème est le suivant. Soit G un graphe connecté, et soit N (G) un complexe simplicial dont les faces sont des sous-ensembles de V qui ont des voisins communs. Ensuite, si N (K) est k-connecté (à savoir, tous ses groupes d'homologie réduits sont de 0 jusqu'à la dimension k-1), alors le nombre de couleurs nécessaires pour colorer G est d'au moins k + 3.

Ne pas avoir un grand ensemble indépendant peut être aussi important que d'avoir une grande clique.

Un obstacle important pour qu'un graphique ne soit pas k-colorable est que la taille maximale d'un ensemble indépendant est inférieure à n / k, où n est le nombre de sommets. Il s'agit d'une obstruction très importante. Par exemple, cela implique qu'un graphe aléatoire en G (n, 1/2) a un nombre chromatique au moins n / log n.

Une obstruction plus précise est que pour chaque attribution de poids non négatifs pour les sommets, il n'y a pas d'ensemble indépendant qui capture une fraction 1/5 (ou plus) du poids total. Notez que cela inclut également les «obstructions sans clique». La dualité LP vous indique que cette obstruction équivaut à ce que le "nombre chromatique fractionnaire" de G soit supérieur à k.

Il existe également des obstacles à la colorabilité k de nature différente qui dépassent parfois la barrière du nombre chromatique fractionnaire. Je leur consacrerai une réponse distincte.

$G$$\chi(G)=k+1$ si et seulement si ...":

$G$$\chi(G)\ge k$$G$$k-1$