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

DOI10.1007/978-3-642-16926-7_28zbMath1309.68102OpenAlexW1571652254MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

\(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

This page was built for publication: The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Degree