Approximability of the upper chromatic number of hypergraphs

DOI10.1016/j.disc.2014.08.007zbMath1315.05047arXiv1310.7964OpenAlexW2071404087WikidataQ59072455 ScholiaQ59072455MaRDI QIDQ2346334

Zsolt Tuza, Csilla Bujtás

Publication date: 1 June 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.7964

zbMATH Keywords

hypergraphhypertreeapproximation ratioC-coloringupper chromatic numbermultiple hitting set

Mathematics Subject Classification ID

Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum number of colors: C-coloring and related problems
• Mixed hypergraphs with bounded degree: Edge-coloring of mixed multigraphs.
• Coloring mixed hypergraphs: theory, algorithms and applications
• On feasible sets of mixed hypergraphs
• Coloring mixed hypertrees
• A threshold of ln n for approximating set cover
• Upper chromatic number of finite projective planes
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• On the minimum size of tight hypergraphs
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
• On approximation properties of the Independent set problem for degree 3 graphs