Bipartite graphs that are not circle graphs

André Bouchet

Annales de l'institut Fourier (1999)

  • Volume: 49, Issue: 3, page 809-814
  • ISSN: 0373-0956

Abstract

top
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.

How to cite

top

Bouchet, André. "Bipartite graphs that are not circle graphs." Annales de l'institut Fourier 49.3 (1999): 809-814. <http://eudml.org/doc/75364>.

@article{Bouchet1999,
abstract = {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 $\{\rm GF\}(2)$.At the end of this short note I briefly recall the work of François Jaeger on circle graphs.},
author = {Bouchet, André},
journal = {Annales de l'institut Fourier},
keywords = {circle graph; binary matroid},
language = {eng},
number = {3},
pages = {809-814},
publisher = {Association des Annales de l'Institut Fourier},
title = {Bipartite graphs that are not circle graphs},
url = {http://eudml.org/doc/75364},
volume = {49},
year = {1999},
}

TY - JOUR
AU - Bouchet, André
TI - Bipartite graphs that are not circle graphs
JO - Annales de l'institut Fourier
PY - 1999
PB - Association des Annales de l'Institut Fourier
VL - 49
IS - 3
SP - 809
EP - 814
AB - 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 ${\rm GF}(2)$.At the end of this short note I briefly recall the work of François Jaeger on circle graphs.
LA - eng
KW - circle graph; binary matroid
UR - http://eudml.org/doc/75364
ER -

References

top
  1. [1] A. BOUCHET, Graphic presentations of isotropic systems, J. Combin. Theory, Ser. B, 45 (1988), 58-76. Zbl0662.05014MR89f:05150
  2. [2] A. BOUCHET, A characterization of unimodular orientations of simple graphs, J. Combin. Theory, Ser. B, 56 (1992), 45-54. Zbl0709.05023MR93i:05092
  3. [3] A. BOUCHET, Circle graph obstructions, J. Combin. Theory, Ser. B, 60 (1994), 107-144. Zbl0793.05116MR95d:05039
  4. [4] H. de FRAYSSEIX, A characterization of circle graphs, Europ. J. Combin., 5 (1984), 223-238. Zbl0551.05056MR86c:05096
  5. [5] E. GASSE, A short proof of a circle graph characterization, Discrete Math., 173 (1997), 277-283. Zbl0882.05111MR98g:05125
  6. [6] F. JAEGER, Graphes de cordes et espaces graphiques, Europ. J. Combin., 4 (1983), 319-327. Zbl0542.05055MR85e:05155
  7. [7] F. JAEGER, On some algebraic properties of graphs, in Progress in Graph Theory (Waterloo, Ont. 1982), Academic Press, Toronto, Ont., 1984, 347-366. Zbl0557.05034MR86d:05074
  8. [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. Zbl0646.05067MR87g:05205
  9. [9] W. NAJI, Reconnaissance des graphes de cordes, Discrete Math., 54 (1985), 329-337. Zbl0567.05033MR87b:05113
  10. [10] K. TRUEMPER, Matroid Decomposition, Academic Press, 1992. Zbl0760.05001MR93h:05046
  11. [11] W. T. TUTTE, Lectures on matroids, J. Res. Nat. Bur. Standards, Sect. B, 69b (1965), 1-47. Zbl0151.33801MR31 #4023

NotesEmbed ?

top

You must be logged in to post comments.