Publication at Faculty of Mathematics and Physics |
2003
Abstract
It is proved that deciding if a given graph is switchig equivalent to a regular graph is NP-complete. The proof is based on a variant of regular hypergraph bicoloring problem.
It is proved that deciding if a given graph is switchig equivalent to a regular graph is NP-complete. The proof is based on a variant of regular hypergraph bicoloring problem.