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

Khelladi, Abdelkader

Annales de l'Institut Fourier, Tome 49 (1999), p. 955-971 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé
Abstract

La généralisation des nombres chromatiques $χ_{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 $χ_{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 $χ_{n}^{0, q} (G)$ . Cette relation s’exprime comme $χ_{n}^{0, q} (G) \geq χ_{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) = {(e, v) \in E \times V; v est incident à e}$ . Un graphe biorienté est un couple $(G, τ)$ où $τ$ est une signature (appelée biorientation) de $H (G)$ , c’est-à-dire une application $τ : H (G) \to {- 1, + 1}$ . Un flot (entier) de $(G, τ)$ 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_{(e, v) \in H (G)} τ (e, v) . f (e) = 0 .$ Un $q$ -flot non nul de $(G, τ)$ est un flot $f$ tel que pour toute arête $e$ de $G, 0 < | f (e) | < q$ . Un $m$ -isthme de $(G, τ)$ 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”.

The generalization of Stahl’s chromatic numbers $χ_{n} (G)$ was a first topic of work with François which ended at the notion of generalized colorings and their associated chromatic numbers denoted $χ_{n}^{p, q} (G)$ . 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 $χ_{n}^{0, q} (G)$ . This relation is written as $χ_{n}^{0, q} (G) \geq χ_{n - 1}^{0, q} (G) + 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 = (V, E)$ is a simple graph, the set of half edges of $G$ is the set denoted $H (G)$ defined by $H (G) = {(e, v) \in E \times V; v is incident to e}$ . A bidirected graph is a couple $(G, τ)$ where $τ$ is a signature (called bidirection) of $H (G)$ , that is a mapping $τ : H (G) \to {- 1, + 1}$ . An (integer) flow of $(G, τ)$ is a valuation of its edges $f : E \to ℤ$ such that for every vertex $v$ of $G$ we have a Kirchoff like relation $\sum_{(e, v) \in H (G)} τ (e, v) . f (e) = 0$ . A nowhere-zero $q$ -flow of $(G, τ)$ is a flow $f$ such that for every edge $e$ of $G, 0 < | f (e) | < q$ . An $m$ -isthmus of $(G, τ)$ 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”.

Publié le : 1999-01-01

MR 2000h:05083 | Zbl 0917.05026

DOI : https://doi.org/10.5802/aif.1701

@article{AIF_1999__49_3_955_0,
     author = {Khelladi, Abdelkader},
     title = {Colorations g\'en\'eralis\'ees, graphes biorient\'es et deux ou trois choses sur Fran\c cois},
     journal = {Annales de l'Institut Fourier},
     volume = {49},
     year = {1999},
     pages = {955-971},
     doi = {10.5802/aif.1701},
     mrnumber = {2000h:05083},
     zbl = {0917.05026},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/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, Tome 49 (1999) pp. 955-971. doi : 10.5802/aif.1701. http://gdmltest.u-ga.fr/item/AIF_1999__49_3_955_0/

Bibliographie

[1] C. Berge, Graphes, Dunod, Paris, 1983. | MR 85a:05001 | Zbl 0531.05031

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

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

[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 83e:05051 | Zbl 0474.05029

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

[6] F. Harary, Graph Theory, Addison-Wesley Publishing Co., Reading, Massachussets, 1976.

[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 88h:05045 | Zbl 0617.90026

[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 81g:05059 | Zbl 0418.05028

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

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

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

[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 0473.05023

[15] T. Zaslavsky, Signed Graphs, Discrete Applied Math., 4 (1982), 47-74. | MR 84e:05095a | Zbl 0476.05080