Two problems in graph theory

摘要: Firstly, two approaches to the problem of finding a minimal edge coloring bipartite graph are presented. These yield algorithms with running times 0(E log D + V log('3) D), and log('2) respectively, where is valence graph. compare favourably 0(min {E V, V('2) V}) time bound due Gabow Kariv. For graphs bounded second algorithm easily modified run in 0(E) time. Secondly, relationship between isomorphism rigidity studied. Although general it not known if these problems equivalent under polynomial Turing reductions, equivalence shown for subclass abelian automorphism groups.