Towards a characterization of bipartite switching classes by means of forbidden subgraphs
Jurriaan Hage ; Tero Harju
Discussiones Mathematicae Graph Theory, Tome 27 (2007), p. 471-483 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2007-01-01
EUDML-ID : urn:eudml:doc:270391 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1374,
     author = {Jurriaan Hage and Tero Harju},
     title = {Towards a characterization of bipartite switching classes by means of forbidden subgraphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {27},
     year = {2007},
     pages = {471-483},
     zbl = {1142.05042},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1374}
}

Jurriaan Hage; Tero Harju. Towards a characterization of bipartite switching classes by means of forbidden subgraphs. Discussiones Mathematicae Graph Theory, Tome 27 (2007) pp. 471-483. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1374/

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

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

[002] [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.

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

[004] [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. | Zbl 1071.05063

[005] [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. | Zbl 1054.05092

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

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

[008] [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]. | Zbl 0138.41702

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