Gabor Elek
Published 2007-11-18, updated 2009-07-02Version 3
Parameter testing algorithms are using constant number of queries to estimate the value of a certain parameter of a very large finite graph. It is well-known that graph parameters such as the independence ratio or the edit-distance from 3-colorability are not testable in bounded degree graphs. We prove, however, that these and several other interesting graph parameters are testable in bounded degree graphs of subexponential growth.
Comments: To appear in Random Structures and Algorithms. (note that the title has changed)
Conflict-free coloring on closed neighborhoods of bounded degree graphs
The Local Structure of Bounded Degree Graphs
Decomposition of bounded degree graphs into $C_4$-free subgraphs
![QR code for arXiv:0711.2800 [math.CO]](http://oss.arxitics.com/images/favicon.svg)