The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Degree

DOI10.1007/978-3-642-16926-7_28zbMath1309.68102MaRDI QIDQ3057634

Edyta Szymańska

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C65: Hypergraphs

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

\(H\)-colorings of dense hypergraphs

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