Preuve du théorème de coloration des lignes de Kőnig ( $\chi'(G) = \Delta(G)$)

Dec 06 2020

J'essaie de trouver une preuve du théorème de coloration des lignes de Kőnig , c'est-à-dire:

L'indice chromatique de tout graphe biparti est égal à son degré maximum

Mais à ma grande surprise, je n'ai * pu trouver que deux questions touchant le sujet:

Coloration des bords des graphes bipartis
La coloration des bords d'un graphe biparti avec un degré maximum de D ne nécessite que des couleurs D

Les graphiques étant le talon d'Achille, je suis incapable d'utiliser les informations contenues dans ce qui précède pour prouver $\chi'(G) = \Delta(G)$ moi même.

* J'ai trouvé de nombreux articles y faisant référence, mais aucun ne le prouve, sauf pour la page 4 de CH6.pdf de la première question, mais je ne pense pas que ce soit suffisant.

Réponses

1 Hendrix Dec 06 2020 at 01:38

Je vais essayer de donner un aperçu des connaissances préalables et d'inclure des sources à chaque étape afin que vous puissiez comprendre séquentiellement. Si vous ne comprenez pas certaines parties (comme la construction à la fin), je vous recommande de travailler quelques petits exemples.

Commençons par présenter le théorème de Hall :

Théorème: (Théorème de Hall) Let $G$ être un graphe biparti avec des parties $A$ et $B$. ensuite$G$ a une correspondance (jeu d'arêtes indépendant) saturant $A$ (chaque sommet de $A$ est le point final d'une arête dans la correspondance) si et seulement si pour chaque $X \subseteq A$ nous avons $|X| \le |N(X)|$.

Les deux sources que je recommande pour une bonne vue du théorème de Hall sont la théorie des graphes de Diestel (qui, si je me souviens bien, donne quatre preuves) et l'Introduction à la théorie des graphes de West.

La signification du théorème de Hall ici est que pour $k$-graphiques bipartites réguliers, nous pouvons trouver une correspondance parfaite. Cela vient de deux choses:

UNE $k$-Le graphique biparti régulier est équilibré .
UNE $k$-Le graphe biparti régulier satisfait la condition de Hall .

Alors maintenant, nous pouvons prouver ce qui suit:

Lemme: Si $G$ est un $k$-graphe bipartite régulier, puis $\chi'(G) = k$.

Nous pouvons utiliser l'induction sur $k$. Par le théorème de Hall,$G$ a une correspondance parfaite $M$. Considérer$G-M$, lequel est $k-1$-régulier (pourquoi?). Par l'hypothèse d'induction,$\chi'(G) = k-1$, et ainsi nous pouvons ajouter $M$ retour comme une nouvelle couleur, étendant ainsi un $k-1$-coloration des bords de $G-M$ à un bon $k$-coloration des bords sur $G$.

Si vous n'êtes pas familier avec l'induction, voici une description différente: Suppression d'une correspondance parfaite d'un $k$-graphe biparti régulier donne un $k-1$-graphe régulier, qui doit aussi avoir une correspondance parfaite ... Itérer ce processus $k$ fois.

Maintenant, pour la ligne d'arrivée. Nous voulons prouver le résultat pour tout graphe bipartite$G$.

Résultat: si $G$ est un graphe biparti, alors $\chi'(G) = \Delta(G)$.

Si $G$est régulier, alors nous sommes faits par le lemme. Sinon, il y a au moins un sommet$v$ dans $G$ avec $\deg(v) < \Delta(G)$. On peut construire un graphe$R$ tel que

$R$ est bipartite.
$R$ est $\Delta(G)$-régulier.
$G \subseteq R$.

Une construction est la suivante. Nous avons$G$ bipartite avec parties $A$ et $B$. Prenez une copie de$G$, dire $G'$ avec des pièces $A'$ et $B'$. Puis pour chaque sommet$v$ pas de diplôme $\Delta(G)$ dans $G$, nous ajoutons un bord entre $v$ et c'est une copie $v' \in G'$. Ce graphique nouvellement obtenu est bipartite avec des parties$A \cup B'$ et $B \cup A'$. Répétez ce processus si nécessaire. Vous remarquerez qu'à chaque itération, l'écart entre le degré minimum et le degré maximum diminue, nous devons donc terminer par un$\Delta(G)$-graphe régulier $R$comme voulu. Vous trouverez que cette construction est celle donnée par le commentaire de Jon Noel ici .

En utilisant le lemme, $\chi'(R) = \Delta(G)$, et donc il y a un $\Delta(G)$-coloration des bords de $R$. Puisque$G \subseteq R$, cette coloration appropriée fonctionne pour $G$. C'est à dire$\chi'(G) = \Delta(G)$.

Quelques notes.

Notez que nous avons utilisé le fait général que $\chi'(H) \le \chi'(G)$ pour $H \subseteq G$ à la fin.

Une chose sur laquelle j'ai jeté un coup d'œil est de savoir si nous autorisons plusieurs bords, mais les choses fonctionnent toujours de cette façon. Si nous autorisons plusieurs arêtes, pouvez-vous voir pourquoi la façon dont nous avons construit$R$ prend exactement $1$itération? Je ne pense pas qu'il y ait de vraie raison d'exclure l'utilisation de plusieurs arêtes.