Coloring bipartite hypergraphs

DOI10.1007/3-540-61310-2_26zbMath1415.90133OpenAlexW1898334569MaRDI QIDQ4645934

Hui Chen, Alan M. Frieze

Publication date: 11 January 2019

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61310-2_26

zbMATH Keywords

polynomial time algorithmadjacency matrixpolynomial timeMarkov inequalitycolor class

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Coloring of graphs and hypergraphs (05C15)

Related Items (11)

Networks beyond pairwise interactions: structure and dynamics ⋮ Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ Unnamed Item ⋮ Concepts on coloring of cluster hypergraphs with application ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors ⋮ Testing hypergraph colorability ⋮ Unnamed Item ⋮ Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs ⋮ An expected polynomial time algorithm for coloring 2-colorable 3-graphs ⋮ Hardness of Rainbow Coloring Hypergraphs

Cites Work

• The complexity of colouring problems on dense graphs
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• Improving the performance guarantee for approximate graph coloring
• Approximate graph coloring by semidefinite programming
• An algorithmic approach to the Lovász local lemma. I
• A Random Recolouring Method for Graphs and Hypergraphs
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Coloring bipartite hypergraphs