The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Degree
From MaRDI portal
Publication:3057634
DOI10.1007/978-3-642-16926-7_28zbMath1309.68102MaRDI QIDQ3057634
Publication date: 16 November 2010
Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-16926-7_28
68Q25: Analysis of algorithms and problem complexity
05C65: Hypergraphs
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Supersaturated graphs and hypergraphs
- Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
- Perfect matchings in large uniform hypergraphs with large minimum collective degree
- The complexity of colouring problems on dense graphs
- The maximum size of 3-uniform hypergraphs not containing a Fano plane
- An expected polynomial time algorithm for coloring 2-colorable 3-graphs
- A Dirac-Type Theorem for 3-Uniform Hypergraphs
- Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs
- The Complexity of Almost Perfect Matchings in Uniform Hypergraphs with High Codegree
- The Complexity of Perfect Matching Problems on Dense Hypergraphs
- On the Complexity of Timetable and Multicommodity Flow Problems
- Approximation and Online Algorithms