no. 3
Bipartite graphs that are not circle graphs
Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 809-814

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.

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},
     year = {1999},
     publisher = {Association des Annales de l'Institut Fourier},
     volume = {49},
     number = {3},
     doi = {10.5802/aif.1693},
     mrnumber = {2000g:05127},
     zbl = {0917.05064},
     language = {en},
     url = {https://www.numdam.org/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  - https://www.numdam.org/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 https://www.numdam.org/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

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

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

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

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

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

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

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

[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. | Zbl | MR

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

[10] K. Truemper, Matroid Decomposition, Academic Press, 1992. | Zbl | MR

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

Cité par Sources :