Voir la notice de l'article provenant de la source Numdam
The homomorphisms of oriented or undirected graphs, the oriented chromatic number, the relationship between acyclic colouring number and oriented chromatic number, have been recently intensely studied. For the purpose of duality, we define the notions of strong-oriented colouring and antisymmetric-flow. An antisymmetric-flow is a flow with values in an additive abelian group which uses no opposite elements of the group. We prove that the strong-oriented chromatic number (as the modular version of oriented chromatic number) is bounded for planar graphs. By duality we obtain that any oriented planar graph has a -antisymmetric-flow. Moreover we prove that any -edge connected oriented graph has an antisymmetric-flow with values in a group whose order depends only of the dimension of the cycle space of the graph . We list several open problems analogous to those for nowhere-zero flows.
Les homomorphismes de graphes orientés ou non orientés, le nombre chromatique orienté, la relation entre le nombre chromatique acyclique et le nombre chromatique orienté, ont été très étudiés ces dernières années. Dans le but de définir des notions duales, nous introduisons les notions de coloration orientée forte et de flot antisymétrique. Un flot antisymétrique est un flot à valeurs dans un groupe abélien qui n’utilise pas d’éléments opposés du groupe. Nous montrons que le nombre chromatique orienté fort (version modulaire du nombre chromatique orienté) est borné pour les graphes planaires; par dualité nous obtenons que tout graphe planaire admet un flot antisymétrique à valeurs dans . Nous prouvons de plus que tout graphe orienté -arête connexe a un flot antisymétrique à valeurs dans un groupe dont l’ordre ne dépend que de la dimension de l’espace des cycles du graphe. Nous terminons par plusieurs problèmes ouverts analogues aux problèmes des flots non-nul.
@article{AIF_1999__49_3_1037_0,
author = {Ne\v{s}et\v{r}ill, J. and Raspaud, Andr\'e},
title = {Antisymmetric flows and strong colourings of oriented graphs},
journal = {Annales de l'Institut Fourier},
pages = {1037--1056},
publisher = {Association des Annales de l{\textquoteright}institut Fourier},
volume = {49},
number = {3},
year = {1999},
doi = {10.5802/aif.1705},
mrnumber = {2002a:05107},
zbl = {0921.05034},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.5802/aif.1705/}
}
TY - JOUR AU - Nešetřill, J. AU - Raspaud, André TI - Antisymmetric flows and strong colourings of oriented graphs JO - Annales de l'Institut Fourier PY - 1999 SP - 1037 EP - 1056 VL - 49 IS - 3 PB - Association des Annales de l’institut Fourier UR - http://geodesic.mathdoc.fr/articles/10.5802/aif.1705/ DO - 10.5802/aif.1705 LA - en ID - AIF_1999__49_3_1037_0 ER -
%0 Journal Article %A Nešetřill, J. %A Raspaud, André %T Antisymmetric flows and strong colourings of oriented graphs %J Annales de l'Institut Fourier %D 1999 %P 1037-1056 %V 49 %N 3 %I Association des Annales de l’institut Fourier %U http://geodesic.mathdoc.fr/articles/10.5802/aif.1705/ %R 10.5802/aif.1705 %G en %F AIF_1999__49_3_1037_0
Nešetřill, J.; Raspaud, André. Antisymmetric flows and strong colourings of oriented graphs. Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 1037-1056. doi: 10.5802/aif.1705
Cité par Sources :