Colorations généralisées, graphes biorientés et deux ou trois choses sur François

Khelladi, Abdelkader. "Colorations généralisées, graphes biorientés et deux ou trois choses sur François." Annales de l'institut Fourier 49.3 (1999): 955-971. <http://eudml.org/doc/75372>.

@article{Khelladi1999,
abstract = {La généralisation des nombres chromatiques $\chi _n(G)$ de Stahl a été un premier thème de travail avec François et a abouti à l’introduction de la notion de colorations généralisées et leurs nombres chromatiques associés, notées $\chi _n^\{p,q\}(G)$. Cette nouvelle notion a permis d’une part, d’infirmer avec Payan une conjecture posée par Brigham et Dutton, et d’autre part, d’étendre de manière naturelle la formule de récurrence de Stahl aux nombres chromatiques $\chi _n^\{0,q\}(G)$. Cette relation s’exprime comme $\chi _n^\{0,q\}(G)\ge \chi _\{n-1\}^\{0,q\}(G)+2$. La conjecture de Bouchet sur les 6-flots non-nuls dans les graphes biorientés a constitué une préoccupation importante de travaux communs avec François. Si $G=(V,E)$ est un graphe simple, l’ensemble des demi-arêtes de $G$ est l’ensemble $H(G)$ défini par $H(G)=\lbrace (e,v)\in E\times V; v~\{\text\{est\} \text\{incident\} \text\{à\}\}~e\rbrace $. Un graphe biorienté est un couple $(G,\tau )$ où $\tau $ est une signature (appelée biorientation) de $H(G)$, c’est-à-dire une application $\tau :H(G)\rightarrow \lbrace -1,+1\rbrace $. Un flot (entier) de $(G,\tau )$ est une valuation de ses arêtes $f:E\rightarrow \{\Bbb Z\}$ telle que pour tout sommet $v$ de $G$ on ait une relation de type Kirchoff $\sum _\{(e,v) \in H(G)\}\tau (e,v). f(e)=0.$ Un $q$-flot non nul de $(G,\tau )$ est un flot $f$ tel que pour toute arête $e$ de $G,~0&lt; \vert f(e)\vert &lt; q$. Un $m$-isthme de $(G,\tau )$ est une arête où tout flot est nul. Le principal résultat porte sur la conjecture de A. Bouchet : “ Tout graphe biorienté sans $m$-isthme admet un 6-flot non nul”.},
author = {Khelladi, Abdelkader},
journal = {Annales de l'institut Fourier},
keywords = {coloring; homomorphism; biorientation; -isthmus; nowhere-zero flow; matroids; circuits},
language = {fre},
number = {3},
pages = {955-971},
publisher = {Association des Annales de l'Institut Fourier},
title = {Colorations généralisées, graphes biorientés et deux ou trois choses sur François},
url = {http://eudml.org/doc/75372},
volume = {49},
year = {1999},
}

TY - JOUR
AU - Khelladi, Abdelkader
TI - Colorations généralisées, graphes biorientés et deux ou trois choses sur François
JO - Annales de l'institut Fourier
PY - 1999
PB - Association des Annales de l'Institut Fourier
VL - 49
IS - 3
SP - 955
EP - 971
AB - La généralisation des nombres chromatiques $\chi _n(G)$ de Stahl a été un premier thème de travail avec François et a abouti à l’introduction de la notion de colorations généralisées et leurs nombres chromatiques associés, notées $\chi _n^{p,q}(G)$. Cette nouvelle notion a permis d’une part, d’infirmer avec Payan une conjecture posée par Brigham et Dutton, et d’autre part, d’étendre de manière naturelle la formule de récurrence de Stahl aux nombres chromatiques $\chi _n^{0,q}(G)$. Cette relation s’exprime comme $\chi _n^{0,q}(G)\ge \chi _{n-1}^{0,q}(G)+2$. La conjecture de Bouchet sur les 6-flots non-nuls dans les graphes biorientés a constitué une préoccupation importante de travaux communs avec François. Si $G=(V,E)$ est un graphe simple, l’ensemble des demi-arêtes de $G$ est l’ensemble $H(G)$ défini par $H(G)=\lbrace (e,v)\in E\times V; v~{\text{est} \text{incident} \text{à}}~e\rbrace $. Un graphe biorienté est un couple $(G,\tau )$ où $\tau $ est une signature (appelée biorientation) de $H(G)$, c’est-à-dire une application $\tau :H(G)\rightarrow \lbrace -1,+1\rbrace $. Un flot (entier) de $(G,\tau )$ est une valuation de ses arêtes $f:E\rightarrow {\Bbb Z}$ telle que pour tout sommet $v$ de $G$ on ait une relation de type Kirchoff $\sum _{(e,v) \in H(G)}\tau (e,v). f(e)=0.$ Un $q$-flot non nul de $(G,\tau )$ est un flot $f$ tel que pour toute arête $e$ de $G,~0&lt; \vert f(e)\vert &lt; q$. Un $m$-isthme de $(G,\tau )$ est une arête où tout flot est nul. Le principal résultat porte sur la conjecture de A. Bouchet : “ Tout graphe biorienté sans $m$-isthme admet un 6-flot non nul”.
LA - fre
KW - coloring; homomorphism; biorientation; -isthmus; nowhere-zero flow; matroids; circuits
UR - http://eudml.org/doc/75372
ER -