Approximability of the upper chromatic number of hypergraphs

DOI10.1016/J.DISC.2014.08.007MaRDI QIDQ2346334zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

approximation ratioC-coloringhypergraphhypertreemultiple hitting setupper chromatic number

Mathematics Subject Classification ID

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

Abstract: A C-coloring of a hypergraph $calH=(X,calE)$ is a vertex coloring $varphi:XomathbbN$ such that each edge $EincalE$ has at least two vertices with a common color. The related parameter $overlinechi(calH)$, called the upper chromatic number of $calH$, is the maximum number of colors can be used in a C-coloring of $calH$. A hypertree is a hypergraph which has a host tree $T$ such that each edge $EincalE$ induces a connected subgraph in $T$. Notations $n$ and $m$ stand for the number of vertices and edges, respectively, in a generic input hypergraph. We establish guaranteed polynomial-time approximation ratios for the difference $n-overlinechi(calH)$, which is $2+2ln(2m)$ on hypergraphs in general, and $1+lnm$ on hypertrees. The latter ratio is essentially tight as we show that $n-overlinechi(calH)$ cannot be approximated within $(1-epsilon)lnm$ on hypertrees (unless $sfNPsubseteqsfDTIME(n^{calO(log;log;n)})$). Furthermore, $overlinechi(calH)$ does not have $calO(n^{1-epsilon})$-approximation and cannot be approximated within additive error $o(n)$ on the class of hypertrees (unless $sfP=sfNP$).

Recommendations

• Maximum number of colors in hypertrees of bounded degree
• Approximate coloring of uniform hypergraphs
• scientific article; zbMATH DE number 1305101
• scientific article; zbMATH DE number 1696541
• scientific article; zbMATH DE number 1491630

Cites work

• A threshold of ln n for approximating set cover
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Coloring mixed hypergraphs: theory, algorithms and applications
• Coloring mixed hypertrees
• Graph theory
• scientific article; zbMATH DE number 3480649 (Why is no real title available?)
• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• scientific article; zbMATH DE number 786134 (Why is no real title available?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Maximum number of colors: C-coloring and related problems
• Mixed hypergraphs with bounded degree: Edge-coloring of mixed multigraphs.
• On approximation properties of the Independent set problem for degree 3 graphs
• On feasible sets of mixed hypergraphs
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
• On the minimum size of tight hypergraphs
• Upper chromatic number of finite projective planes
• Voloshin's conjecture for C-perfect hypertrees

Cited in

(5)

• Upper bound in the Erdős-Hajnal problem of hypergraph coloring
• A primal-dual property of the upper chromatic number of mixed hypergraphs
• Maximum number of colors in hypertrees of bounded degree
• Approximations to m‐Colored Complete Infinite Hypergraphs
• On the hardness of approximating the chromatic number

This page was built for publication: Approximability of the upper chromatic number of hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2346334)