Chordal graphs are easily testable

2019/02/16 by de Verclos, Rémi de Joannis · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1902.06135

Abstract

We prove that the class of chordal graphs is easily testable in the following sense. There exists a constant c>0 such that, if adding/removing at most εn² edges to a graph G with n vertices does not make it chordal, then a set of (1/ε)^c vertices of G chosen uniformly at random induces a graph that is not chordal with probability at least 1/2. This answers a question of Gishboliner and Shapira.

Cited by

• Polynomial Property Testing

Related

• Sampling Unlabeled Chordal Graphs in Expected Polynomial Time
• Generating Weakly Chordal Graphs from Arbitrary Graphs
• An Algorithm for Generating Strongly Chordal Graphs
• Every Minor-Closed Property of Sparse Graphs is Testable
• Planar Graphs: Random Walks and Bipartiteness Testing