Voir la notice de l'article provenant de la source Numdam
The following result is proved: if a bipartite graph is not a circle graph, then its complement is not a circle graph. The proof uses Naji’s characterization of circle graphs by means of a linear system of equations with unknowns in .
At the end of this short note I briefly recall the work of François Jaeger on circle graphs.
Nous prouvons le résultat suivant : si un graphe biparti n’est pas un graphe de cordes, alors son complément n’est pas un graphe de cordes. La preuve fait appel à une caractérisation des graphes de cordes par Naji, qui utilise un système d’équations linéaires sur le corps à deux éléments.
À la fin de cette note je rappelle brièvement le travail de François Jaeger sur les graphes de cordes.
@article{AIF_1999__49_3_809_0,
author = {Bouchet, Andr\'e},
title = {Bipartite graphs that are not circle graphs},
journal = {Annales de l'Institut Fourier},
pages = {809--814},
publisher = {Association des Annales de l{\textquoteright}institut Fourier},
volume = {49},
number = {3},
year = {1999},
doi = {10.5802/aif.1693},
mrnumber = {2000g:05127},
zbl = {0917.05064},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.5802/aif.1693/}
}
TY - JOUR AU - Bouchet, André TI - Bipartite graphs that are not circle graphs JO - Annales de l'Institut Fourier PY - 1999 SP - 809 EP - 814 VL - 49 IS - 3 PB - Association des Annales de l’institut Fourier UR - http://geodesic.mathdoc.fr/articles/10.5802/aif.1693/ DO - 10.5802/aif.1693 LA - en ID - AIF_1999__49_3_809_0 ER -
%0 Journal Article %A Bouchet, André %T Bipartite graphs that are not circle graphs %J Annales de l'Institut Fourier %D 1999 %P 809-814 %V 49 %N 3 %I Association des Annales de l’institut Fourier %U http://geodesic.mathdoc.fr/articles/10.5802/aif.1693/ %R 10.5802/aif.1693 %G en %F AIF_1999__49_3_809_0
Bouchet, André. Bipartite graphs that are not circle graphs. Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 809-814. doi: 10.5802/aif.1693
Cité par Sources :