Testing hypergraph colorability

DOI10.1016/j.tcs.2004.09.031zbMath1070.68117OpenAlexW2090435360MaRDI 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 testingHypergraphsHypergraph coloringHypergraph algorithms

Mathematics Subject Classification ID

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

Related Items (3)

Unavoidable tournaments ⋮ Distribution-free connectivity testing for sparse graphs ⋮ Testing Euclidean Spanners

Cites Work

• 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
• [https://portal.mardi4nfdi.de/wiki/Publication:4521547 Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma]
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Testing hypergraph colorability