Testing hypergraph colorability

DOI10.1016/J.TCS.2004.09.031MaRDI QIDQ1770424zbMATH OpenOpenAlexFDO

Authors Artur Czumaj, Christian Sohler

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

HypergraphsProperty testingHypergraph coloringHypergraph algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Recommendations

• scientific article; zbMATH DE number 1754615
• Testing graphs for colorability properties*
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Testing \(k\)-colorability
• Every Monotone 3‐Graph Property is Testable

Cites work

• scientific article; zbMATH DE number 1670655 (Why is no real title available?)
• scientific article; zbMATH DE number 1002208 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 1241385 (Why is no real title available?)
• scientific article; zbMATH DE number 1301963 (Why is no real title available?)
• scientific article; zbMATH DE number 1305101 (Why is no real title available?)
• scientific article; zbMATH DE number 1857651 (Why is no real title available?)
• A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)
• A sublinear bipartiteness tester for bounded degree graphs
• Abstract Combinatorial Programs and Efficient Property Testers
• An algorithmic approach to the Lovász local lemma. I
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs
• Balanced Allocations
• Coloring bipartite hypergraphs
• Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
• Efficient testing of large graphs
• On graphs with small subgraphs of large chromatic number
• Property testers for dense constraint satisfaction programs on finite domains
• Property testing and its connection to learning and approximation
• Quick approximation to matrices and applications
• Random sampling and approximation of MAX-CSP problems
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• Testing \(k\)-colorability
• Testing graphs for colorability properties
• Testing metric properties
• Testing of matrix properties
• Testing properties of directed graphs: acyclicity and connectivity*
• Testing satisfiability

Cited in

(11)

• Hypergraph coloring and reconfigured RAM testing
• Unavoidable tournaments
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A proof of Green's conjecture regarding the removal properties of sets of linear equations
• Comparing the strength of query types in property testing: the case of testing \(k\)-colorability
• Testing Euclidean Spanners
• Testing graphs for colorability properties
• Distribution-free connectivity testing for sparse graphs
• scientific article; zbMATH DE number 1754615 (Why is no real title available?)
• scientific article; zbMATH DE number 2119722 (Why is no real title available?)
• Testing \(k\)-colorability

This page was built for publication: Testing hypergraph colorability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1770424)