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

Jurriaan Hage; Tero Harju

Discussiones Mathematicae Graph Theory (2007)

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

Abstract

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

How to cite

top

Jurriaan 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. [1] D.G. Corneil and R.A. Mathon, Geometry and Combinatorics: Selected Works of J.J. Seidel (Academic Press, Boston, 1991). 
  2. [2] A. Ehrenfeucht, T. Harju and G. Rozenberg, The Theory of 2-Structures (World Scientific, Singapore, 1999). Zbl0981.05002
  3. [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. [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. [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. [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. [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. [8] E. Spence, Tables of Two-graphs, http://gauss.maths.gla.ac.uk/ted/. Zbl0857.05069
  9. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.