We briefly discuss a few open problems in the study of various models of testing graph properties, focusing on the query complexity of the various tasks. In the dense graph model, we discuss several open problems, including:
* Determining the complexity of testing triangle-freeness.
* Characterizing the class of properties that are testable within extremely low complexity.
Turning to the bounded-degree graph model, we discuss several open problems, including:
* Characterizing the class of properties that are testable within size-oblivious complexity.
* Determining the complexity of graph isomorphism.
In each of the foregoing models, we also discuss a favorite open problem that was recently resolved. Lastly, we discuss the vast lack of knowledge with respect to testing graph properties in the general graph model.
Correcting a typo (in Sec 3.2) and adding Footnote 12 relating to it.
We briefly discuss a few open problems in the study of various models of testing graph properties, focusing on the query complexity of the various tasks. In the dense graph model, we discuss several open problems, including:
* Determining the complexity of testing triangle-freeness.
* Characterizing the class of properties that are testable within extremely low complexity.
Turning to the bounded-degree graph model, we discuss several open problems, including:
* Characterizing the class of properties that are testable within size-oblivious complexity.
* Determining the complexity of graph isomorphism.
In each of the foregoing models, we also discuss a favorite open problem that was recently resolved. Lastly, we discuss the vast lack of knowledge with respect to testing graph properties in the general graph model.