Testing graphs for colorability properties
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].
- Functions that have read-once branching programs of quadratic size are not necessarily testable
- A large lower bound on the query complexity of a simple Boolean function
- Testing hypergraph colorability
- Testing of matrix-poset properties
- Testing k-colorability
- Hypergraph coloring and reconfigured RAM testing
- Functions that have read‐twice constant width branching programs are not necessarily testable
- Testing graphs for colorability properties*
- Testing permutation properties through subpermutations
This page was built for publication: Testing graphs for colorability properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2768393)
