Estimating the distance to a hereditary graph property

Mar 14, 2018

Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann and Henrique Stagni

Given a family of graphs "F", we prove that the distance to being induced "F"-free is estimable with a query complexity that depends only on the bounds of the Frieze-Kannan Regularity Lemma and a Removal Lemma for "F".

The whole paper is available here.

Share on Twitter Share on Facebook