no. 3
Bipartite graphs that are not circle graphs
Annales de l'Institut Fourier, Volume 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.

Bouchet, André. Bipartite graphs that are not circle graphs. Annales de l'Institut Fourier, Volume 49 (1999) no. 3, pp. 809-814. doi: 10.5802/aif.1693
@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{\textquoteright}institut Fourier},
     volume = {49},
     number = {3},
     doi = {10.5802/aif.1693},
     zbl = {0917.05064},
     mrnumber = {2000g:05127},
     language = {en},
     url = {https://aif.centre-mersenne.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://aif.centre-mersenne.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://aif.centre-mersenne.org/articles/10.5802/aif.1693/
%R 10.5802/aif.1693
%G en
%F AIF_1999__49_3_809_0

[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

Cited by Sources: