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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.