# Towards a characterization of bipartite switching classes by means of forbidden subgraphs

Discussiones Mathematicae Graph Theory (2007)

- Volume: 27, Issue: 3, page 471-483
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJurriaan Hage, and Tero Harju. "Towards a characterization of bipartite switching classes by means of forbidden subgraphs." Discussiones Mathematicae Graph Theory 27.3 (2007): 471-483. <http://eudml.org/doc/270391>.

@article{JurriaanHage2007,

abstract = {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.},

author = {Jurriaan Hage, Tero Harju},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {switching classes; bipartite graphs; forbidden subgraphs; combinatorial search},

language = {eng},

number = {3},

pages = {471-483},

title = {Towards a characterization of bipartite switching classes by means of forbidden subgraphs},

url = {http://eudml.org/doc/270391},

volume = {27},

year = {2007},

}

TY - JOUR

AU - Jurriaan Hage

AU - Tero Harju

TI - Towards a characterization of bipartite switching classes by means of forbidden subgraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2007

VL - 27

IS - 3

SP - 471

EP - 483

AB - 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.

LA - eng

KW - switching classes; bipartite graphs; forbidden subgraphs; combinatorial search

UR - http://eudml.org/doc/270391

ER -

## References

top- [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). Zbl0981.05002
- [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. Zbl1173.68511
- [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. Zbl1071.05063
- [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. Zbl1054.05092
- [7] A. Hertz, On perfect switching classes, Discrete Applied Math. 89 (1998) 263-267, doi: 10.1016/S0166-218X(98)00134-6. Zbl0918.05055
- [8] E. Spence, Tables of Two-graphs, http://gauss.maths.gla.ac.uk/ted/. Zbl0857.05069
- [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]. Zbl0138.41702
- [10] T. Zaslavsky, A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas, Electronic J. Combin., 1999. Dynamic Survey No. DS8. Zbl0898.05001

## NotesEmbed ?

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