Testing graphs for colorability properties (Q2768393)

If \({\mathcal F}\) is a family of \(c\)-colored graphs, \(\alpha_1,\dots,\alpha_c\) are nonnegative reals summing up to 1, a graph \(G\) on \(n\) vertices is \((\alpha,{\mathcal F})\) colorable if \(G\) has an \({\mathcal F}\) coloring such that the number of vertices with color \(i\) is \(\lfloor\alpha_i n\rfloor\) or \(\lceil\alpha_i n\rceil\). This property is testable in the sense that for any \(\varepsilon>0\) there is a randomized algorithm of fixed length asking the edges of the input graph \(G\) and distinguishing, with high probability, between the case that \(G\) has the property and the case that \(G\) needs at least \(\varepsilon {n\choose 2}\) edges to be altered to get a graph having the property. The statement and the proof are generalized to the case when the pairs are colored with \(c>2\) colors and again some finitely many colorings are excluded as induced colorings. The proofs heavily use Szemerédi's regularity lemma.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].