Publikace na Matematicko-fyzikální fakulta |
2003
Abstrakt
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.