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 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2007},
     volume = {27},
     number = {3},
     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
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
%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/

[1] D.G. Corneil and R.A. Mathon, Geometry and Combinatorics: Selected Works of J.J. Seidel (Academic Press, Boston, 1991).

[2] A. Ehrenfeucht, T. Harju and G. Rozenberg, The Theory of 2-Structures (World Scientific, Singapore, 1999).

[3] J. Hage, Structural Aspects Of Switching Classes (PhD thesis, Leiden Institute of Advanced Computer Science, 2001) http://www.cs.uu.nl/people/jur/2s.html.

[4] J. Hage, Enumerating submultisets of multisets, Inf. Proc. Letters 85 (2003) 221-226, doi: 10.1016/S0020-0190(02)00394-0.

[5] J. Hage and T. Harju, A characterization of acyclic switching classes using forbidden subgraphs, SIAM J. Discrete Math. 18 (2004) 159-176, doi: 10.1137/S0895480100381890.

[6] J. Hage and T. Harju and E. Welzl, Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes, Fundamenta Informaticae 58 (2003) 23-37.

[7] A. Hertz, On perfect switching classes, Discrete Applied Math. 89 (1998) 263-267, doi: 10.1016/S0166-218X(98)00134-6.

[8] E. Spence, Tables of Two-graphs, http://gauss.maths.gla.ac.uk/ted/.

[9] J.H. van Lint and J.J. Seidel, Equilateral points in elliptic geometry, Proc. Kon. Nederl. Acad. Wetensch. (A) 69 (1966) 335-348. Reprinted in [1].

[10] T. Zaslavsky, A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas, Electronic J. Combin., 1999. Dynamic Survey No. DS8.