Bipartite graphs that are not circle graphs

Authors
Bouchet, A
Citation
A. Bouchet, Bipartite graphs that are not circle graphs, ANN I FOUR, 49(3), 1999, pp. 809
Citations number
11
Categorie Soggetti
Mathematics
Journal title
ANNALES DE L INSTITUT FOURIER
ISSN journal
03730956 → ACNP
Volume
49
Issue
3
Year of publication
1999
Database
ISI
SICI code
0373-0956(1999)49:3<809:BGTANC>2.0.ZU;2-O
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 characte rization of circle graphs by means of a linear system of equations with unk nowns in GF(2). At the end of this short note I briefly recall the work of Francois Jaeger on circle graphs.