Colorations généralisées, graphes biorientés et deux ou trois choses sur François
Annales de l'Institut Fourier, Volume 49 (1999) no. 3, pp. 955-971.

The generalization of Stahl’s chromatic numbers ${\chi }_{n}\left(G\right)$ was a first topic of work with François which ended at the notion of generalized colorings and their associated chromatic numbers denoted ${\chi }_{n}^{p,q}\left(G\right)$. This notion allowed, in one hand to infirm with Payan a conjecture of Brigham and Dutton, and on the other hand to extend in a natural way Stahl’s recurrence relation to the chromatic numbers ${\chi }_{n}^{0,q}\left(G\right)$. This relation is written as ${\chi }_{n}^{0,q}\left(G\right)\ge {\chi }_{n-1}^{0,q}\left(G\right)+2$. Bouchet’s conjecture on the nowhere-zero 6-flow in bidirected graphs was an important topic of common research with François. If $G=\left(V,E\right)$ is a simple graph, the set of half edges of $G$ is the set denoted $H\left(G\right)$ defined by $H\left(G\right)=\left\{\left(e,v\right)\in E×V;v\phantom{\rule{3.33333pt}{0ex}}\text{is}\phantom{\rule{4pt}{0ex}}\text{incident}\phantom{\rule{4pt}{0ex}}\text{to}\phantom{\rule{3.33333pt}{0ex}}e\right\}$. A bidirected graph is a couple $\left(G,\tau \right)$ where $\tau$ is a signature (called bidirection) of $H\left(G\right)$, that is a mapping $\tau :H\left(G\right)\to \left\{-1,+1\right\}$. An (integer) flow of $\left(G,\tau \right)$ is a valuation of its edges $f:E\to ℤ$ such that for every vertex $v$ of $G$ we have a Kirchoff like relation ${\sum }_{\left(e,v\right)\in H\left(G\right)}\tau \left(e,v\right).f\left(e\right)=0$. A nowhere-zero $q$-flow of $\left(G,\tau \right)$ is a flow $f$ such that for every edge $e$ of $G,\phantom{\rule{3.33333pt}{0ex}}0<|f\left(e\right)|. An $m$-isthmus of $\left(G,\tau \right)$ is an edge where every flow takes value zero. The principal result obtained is on Bouchet’s conjecture : “Every bidirected graph without $m$-isthmus has a nowhere-zero 6-flow”.

La généralisation des nombres chromatiques ${\chi }_{n}\left(G\right)$ 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}\left(G\right)$. 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}\left(G\right)$. Cette relation s’exprime comme ${\chi }_{n}^{0,q}\left(G\right)\ge {\chi }_{n-1}^{0,q}\left(G\right)+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=\left(V,E\right)$ est un graphe simple, l’ensemble des demi-arêtes de $G$ est l’ensemble $H\left(G\right)$ défini par $H\left(G\right)=\left\{\left(e,v\right)\in E×V;v\phantom{\rule{3.33333pt}{0ex}}\text{est}\phantom{\rule{4pt}{0ex}}\text{incident}\phantom{\rule{4pt}{0ex}}\text{à}\phantom{\rule{3.33333pt}{0ex}}e\right\}$. Un graphe biorienté est un couple $\left(G,\tau \right)$$\tau$ est une signature (appelée biorientation) de $H\left(G\right)$, c’est-à-dire une application $\tau :H\left(G\right)\to \left\{-1,+1\right\}$. Un flot (entier) de $\left(G,\tau \right)$ est une valuation de ses arêtes $f:E\to ℤ$ telle que pour tout sommet $v$ de $G$ on ait une relation de type Kirchoff ${\sum }_{\left(e,v\right)\in H\left(G\right)}\tau \left(e,v\right).f\left(e\right)=0.$ Un $q$-flot non nul de $\left(G,\tau \right)$ est un flot $f$ tel que pour toute arête $e$ de $G,\phantom{\rule{3.33333pt}{0ex}}0<|f\left(e\right)|. Un $m$-isthme de $\left(G,\tau \right)$ 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”.

@article{AIF_1999__49_3_955_0,
title = {Colorations g\'en\'eralis\'ees, graphes biorient\'es et deux ou trois choses sur {Fran\c{c}ois}},
journal = {Annales de l'Institut Fourier},
pages = {955--971},
publisher = {Association des Annales de l{\textquoteright}institut Fourier},
volume = {49},
number = {3},
year = {1999},
doi = {10.5802/aif.1701},
mrnumber = {2000h:05083},
zbl = {0917.05026},
language = {fr},
url = {http://archive.numdam.org/articles/10.5802/aif.1701/}
}
TY  - JOUR
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
SP  - 955
EP  - 971
VL  - 49
IS  - 3
PB  - Association des Annales de l’institut Fourier
UR  - http://archive.numdam.org/articles/10.5802/aif.1701/
DO  - 10.5802/aif.1701
LA  - fr
ID  - AIF_1999__49_3_955_0
ER  - 
%0 Journal Article
%T Colorations généralisées, graphes biorientés et deux ou trois choses sur François
%J Annales de l'Institut Fourier
%D 1999
%P 955-971
%V 49
%N 3
%I Association des Annales de l’institut Fourier
%U http://archive.numdam.org/articles/10.5802/aif.1701/
%R 10.5802/aif.1701
%G fr
%F AIF_1999__49_3_955_0
Khelladi, Abdelkader. Colorations généralisées, graphes biorientés et deux ou trois choses sur François. Annales de l'Institut Fourier, Volume 49 (1999) no. 3, pp. 955-971. doi : 10.5802/aif.1701. http://archive.numdam.org/articles/10.5802/aif.1701/

[1] C. Berge, Graphes, Dunod, Paris, 1983. | MR | Zbl

[2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976. | Zbl

[3] A. Bouchet, Nowhere-zero integral flows on a bidirect graph, J. Combin. Theory, Ser. B, 34 (1983), 279-292. | MR | Zbl

[4] R.C. Brigham, R.D. Dutton, Generalized k-tuple Colorings of Cycles and other Graphs, J. Combin. Theory, Ser. B, 32 (1982), 90-94. | MR | Zbl

[5] F. Harary, On the notion of balance of a signed graph, Michigan Math., J., 2 (1953-1954), 143-146. | MR | Zbl

[7] F. Jaeger, Thèse de Doctorat d'État, USMG, Grenoble, France (juin 1976).

[8] A. Khelladi, Nowhere-Zero Integral Chains and Flows in Bidirected Graphs, J. Comb. Theory, Ser. B, 43 (1987), 95-115. | MR | Zbl

[9] A. Khelladi, Thèse de Doctorat d'État, USTHB, Alger, Algérie, (mai 1985).

[10] L. Lovász, Kneser Conjecture, chromatic number, and homotopy, J. Combin. Theory, Ser. A, 25 (1978), 319-324. | MR | Zbl

[11] P.D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory, Ser. B, 28 (1981), 130-131. | MR | Zbl

[12] S. Stahl, n-Tuple colorings and associated graphs, J. Combin. Theory, Ser. B, 20 (1976), 185-203. | MR | Zbl

[13] W.T. Tutte, A class of Abelian Groups, Can. J. Math., 8 (1952), 13-28. | MR | Zbl

[14] W.T. Tutte, On chain-groups and the factors of graphs, In Algebraic Methods in Graph Theory (Szeged, 1978), vol. 25 of Colloq. Math. Soc. Janos Bolyai, 793-818, North-Holland, Amsterdam, 1981. | Zbl

[15] T. Zaslavsky, Signed Graphs, Discrete Applied Math., 4 (1982), 47-74. | MR | Zbl

Cited by Sources: