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

Jurriaan Hage | Zendy; Tero Harju | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Jurriaan Hage,

Tero Harju

Publication year - 2007

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1374

Subject(s) - bipartite graph , mathematics , characterization (materials science) , combinatorics , discrete mathematics , graph , nanotechnology , materials science

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research