Geodesic
Towards a characterization of bipartite switching classes by means of forbidden subgraphs
Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 3, pp. 471-483

Voir la notice de l'article provenant de la source Library of Science

We investigate which switching classes do not contain a bipartite graph. Our final aim is a characterization by means of a set of critically non-bipartite graphs: they do not have a bipartite switch, but every induced proper subgraph does. In addition to the odd cycles, we list a number of exceptional cases and prove that these are indeed critically non-bipartite. Finally, we give a number of structural results towards proving the fact that we have indeed found them all. The search for critically non-bipartite graphs was done using software written in C and Scheme. We report on our experiences in coping with the combinatorial explosion.
Keywords: switching classes, bipartite graphs, forbidden subgraphs, combinatorial search 
@article{DMGT_2007_27_3_a5,
     author = {Hage, Jurriaan and Harju, Tero},
     title = {Towards a characterization of bipartite switching classes by means of forbidden subgraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {471--483},
     publisher = {mathdoc},
     volume = {27},
     number = {3},
     year = {2007},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2007_27_3_a5/}
}
TY  - JOUR
AU  - Hage, Jurriaan
AU  - Harju, Tero
TI  - Towards a characterization of bipartite switching classes by means of forbidden subgraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2007
SP  - 471
EP  - 483
VL  - 27
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2007_27_3_a5/
LA  - en
ID  - DMGT_2007_27_3_a5
ER  - 
%0 Journal Article
%A Hage, Jurriaan
%A Harju, Tero
%T Towards a characterization of bipartite switching classes by means of forbidden subgraphs
%J Discussiones Mathematicae. Graph Theory
%D 2007
%P 471-483
%V 27
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2007_27_3_a5/
%G en
%F DMGT_2007_27_3_a5
Hage, Jurriaan; Harju, Tero. Towards a characterization of bipartite switching classes by means of forbidden subgraphs. Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 3, pp. 471-483. http://geodesic.mathdoc.fr/item/DMGT_2007_27_3_a5/