Testing graphs for colorability properties

MaRDI QIDQ2768393zbMATH OpenFDO

Authors Eldar Fischer

Publication date 26 October 2003

zbMATH Keywords

graph algorithmsgraph coloringsregularity lemma

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05)

Recommendations

• Testing graphs for colorability properties*
• Testing k-colorability
• Every Monotone Graph Property Is Testable
• Efficient testing of large graphs
• Testing hypergraph colorability

Cited in

(9)

• 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)