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.
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.
| Original language | English |
|---|---|
| Publisher | Department of Information and Computing Sciences, Utrecht University |
| Number of pages | 15 |
| Publication status | Published - 2006 |
Publication series
| Name | Technical Report Series |
|---|---|
| No. | UU-CS-2006-028 |