Testing graphs for colorability properties*

DOI10.1002/RSA.20037MaRDI QIDQ4680410zbMATH OpenOpenAlexFDO

Authors Eldar Fischer

Publication date 1 June 2005

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20037

zbMATH Keywords

graph coloringregularity lemmaproperty testing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Efficient testing of large graphs
• Testing graphs for colorability properties
• Testing k-colorability
• On the testability of graph partition properties
• scientific article; zbMATH DE number 1754615

Cites work

• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• Testing of matrix properties

Cited in

(16)

• Hypergraph coloring and reconfigured RAM testing
• Efficient testing of large graphs
• On the testability of graph partition properties
• Comparing the strength of query types in property testing: the case of testing \(k\)-colorability
• Earthmover Resilience and Testing in Ordered Structures
• Testable and untestable classes of first-order formulae
• Indistinguishability and First-Order Logic
• On the benefits of adaptivity in property testing of dense graphs
• Testing graphs for colorability properties
• Comparing the strength of query types in property testing: the case of \(k\)-colorability
• Testing hypergraph colorability
• Easily testable graph properties
• A note on the testability of Ramsey's class
• scientific article; zbMATH DE number 1754615 (Why is no real title available?)
• Non-deterministic graph property testing
• Testing k-colorability

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