Testing hypergraph colorability

DOI10.1016/j.tcs.2004.09.031zbMath1070.68117MaRDI QIDQ1770424

Christian Sohler, Artur Czumaj

Publication date: 6 April 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.09.031

zbMATH Keywords

Property testing; Hypergraphs; Hypergraph coloring; Hypergraph algorithms

Mathematics Subject Classification ID

05C65: Hypergraphs

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Distribution-free connectivity testing for sparse graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On graphs with small subgraphs of large chromatic number
• Quick approximation to matrices and applications
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• A sublinear bipartiteness tester for bounded degree graphs
• Testing k-colorability
• Property testers for dense constraint satisfaction programs on finite domains
• Property testing and its connection to learning and approximation
• A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)
• Random sampling and approximation of MAX-CSP problems
• An algorithmic approach to the Lovász local lemma. I
• Balanced Allocations
• Testing satisfiability
• Testing properties of directed graphs: acyclicity and connectivity*
• Coloring bipartite hypergraphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing metric properties
• Testing of matrix properties
• Abstract Combinatorial Programs and Efficient Property Testers
• Efficient testing of large graphs