Bipartite graphs that are not circle graphs
Bouchet, André
Annales de l'Institut Fourier, Tome 49 (1999), p. 809-814 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

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 GF (2).

At the end of this short note I briefly recall the work of François Jaeger on circle graphs.

@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},
     volume = {49},
     year = {1999},
     pages = {809-814},
     doi = {10.5802/aif.1693},
     mrnumber = {2000g:05127},
     zbl = {0917.05064},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_1999__49_3_809_0}
}

Bouchet, André. Bipartite graphs that are not circle graphs. Annales de l'Institut Fourier, Tome 49 (1999) pp. 809-814. doi : 10.5802/aif.1693. http://gdmltest.u-ga.fr/item/AIF_1999__49_3_809_0/

[1] A. Bouchet, Graphic presentations of isotropic systems, J. Combin. Theory, Ser. B, 45 (1988), 58-76. | MR 89f:05150 | Zbl 0662.05014

[2] A. Bouchet, A characterization of unimodular orientations of simple graphs, J. Combin. Theory, Ser. B, 56 (1992), 45-54. | MR 93i:05092 | Zbl 0709.05023

[3] A. Bouchet, Circle graph obstructions, J. Combin. Theory, Ser. B, 60 (1994), 107-144. | MR 95d:05039 | Zbl 0793.05116

[4] H. De Fraysseix, A characterization of circle graphs, Europ. J. Combin., 5 (1984), 223-238. | MR 86c:05096 | Zbl 0551.05056

[5] E. Gasse, A short proof of a circle graph characterization, Discrete Math., 173 (1997), 277-283. | MR 98g:05125 | Zbl 0882.05111

[6] F. Jaeger, Graphes de cordes et espaces graphiques, Europ. J. Combin., 4 (1983), 319-327. | MR 85e:05155 | Zbl 0542.05055

[7] F. Jaeger, On some algebraic properties of graphs, in Progress in Graph Theory (Waterloo, Ont. 1982), Academic Press, Toronto, Ont., 1984, 347-366. | MR 86d:05074 | Zbl 0557.05034

[8] F. Jaeger, Graphic description of binary spaces, in Matroid Theory (Szeged, 1982), vol. 40 of Colloq. Math. Soc. Janos Bolyai, North-Holland, Amsterdam (1985), 215-231. | MR 87g:05205 | Zbl 0646.05067

[9] W. Naji, Reconnaissance des graphes de cordes, Discrete Math., 54 (1985), 329-337. | MR 87b:05113 | Zbl 0567.05033

[10] K. Truemper, Matroid Decomposition, Academic Press, 1992. | MR 93h:05046 | Zbl 0760.05001

[11] W. T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Standards, Sect. B, 69b (1965), 1-47. | MR 31 #4023 | Zbl 0151.33801