Article ID: | iaor20111360 |
Volume: | 21 |
Issue: | 1 |
Start Page Number: | 19 |
End Page Number: | 46 |
Publication Date: | Jan 2011 |
Journal: | Journal of Combinatorial Optimization |
Authors: | Gavoille Cyril, Courcelle Bruno, Kant Moustapha |
We consider graph properties that can be checked from labels, i.e., bit sequences, of logarithmic length attached to vertices. We prove that there exists such a labeling for checking a first‐order formula with free set variables in the graphs of every class that is