Download PDF - Towards a characterization of bipartite switching classes by means of forbidden subgraphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

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

Authors 1, 2

Affiliations

  1. Department of Information, and Computing Sciences, University Utrecht, P.O. Box 80.089, 3508 TB Utrecht, Netherlands
  2. 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

ENG
switching classes, bipartite graphs, forbidden subgraphs, combinatorial search

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2007/27/3
Export to PBN, Opens in new tab
Pages:
471-483
Main language of publication
English
Received
2006-05-19
Accepted
2007-06-13
Published
2007

DOI: 10.7151/dmgt.1374

Exact and natural sciences