An Optimal Algorithm for Computing Frieze-Kannan Regular Partitions

Abstract

In this paper we prove that two local conditions involving the degrees and co-degrees in a graph can be used to determine whether a given vertex partition is Frieze–Kannan regular. With a more refined version of these two local conditions we provide a deterministic algorithm that obtains a Frieze–Kannan regular partition of any graph $G$ in time $O(|V(G)|^2)$.

Publication
Combinatorics, Probability and Computing, 24(2), pages 407–437
Date