Estimating the distance to a hereditary graph property

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.

 

NeuroMat

The Research, Innovation and Dissemination Center for Neuromathematics is hosted by the University of São Paulo and funded by FAPESP (São Paulo Research Foundation).

 

User login

 

Contact

Address:
1010 Matão Street - Cidade Universitária - São Paulo - SP - Brasil. 05508-090. See map.

Phone:
55 11 3091-1717

General contact email:
neuromat@numec.prp.usp.br

Media inquiries email:
comunicacao@numec.prp.usp.br