DMGT

Discussiones Mathematicae Graph Theory 27(3) (2007) 471-483
DOI: https://doi.org/10.7151/dmgt.1374

TOWARDS A CHARACTERIZATION OF BIPARTITE SWITCHING CLASSES BY MEANS OF FORBIDDEN SUBGRAPHS

Jurriaan Hage

Department of Information
and Computing Sciences, University Utrecht
P.O. Box 80.089, 3508 TB Utrecht, Netherlands
e-mail: jur@cs.uu.nl

Tero Harju

Department of Mathematics
University of Turku
FIN-20014 Turku, Finland

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.

Keywords: switching classes, bipartite graphs, forbidden subgraphs, combinatorial search.

2000 Mathematics Subject Classification: 05C22, 05C75.

References

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

Received 19 May 2006
Revised 13 June 2007
Accepted 13 June 2007