Bicoloring covers for graphs and hypergraphs

MaRDI QIDQ6257773zbMATH OpenFDO

Authors Tapas Kumar Mishra, Sudebkumar Prasant Pal

Publication date 1 January 2015

Mathematics Subject Classification ID

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

Abstract: Let the {it bicoloring cover number $ch{i}^c(G)$} for a hypergraph $G(V,E)$ be the minimum number of bicolorings of vertices of $G$ such that every hyperedge $einE$ of $G$ is properly bicolored in at least one of the $ch{i}^c(G)$ bicolorings. We investigate the relationship between $ch{i}^c(G)$, matchings, hitting sets, $alpha(G)$(independence number) and $chi(G)$ (chromatic number). We design a factor $O(fraclognloglogn-logloglogn)$ approximation algorithm for computing a bicoloring cover. We define a new parameter for hypergraphs - "cover independence number $gamma(G)$" and prove that $logfrac|V|gamma(G)$ and $frac|V|2gamma(G)$ are lower bounds for $ch{i}^c(G)$ and $chi(G)$, respectively. We show that $ch{i}^c(G)$ can be approximated by a polynomial time algorithm achieving approximation ratio $frac11-t$, if $gamma(G)=n^t$, where $t<1$. We also construct a particular class of hypergraphs $G(V,E)$ called {it cover friendly} hypergraphs where the ratio of $alpha(G)$ to $gamma(G)$ can be arbitrarily large.We prove that for any $tgeq1$, there exists a $k$-uniform hypergraph $G$ such that the {it clique number} $omega(G)=k$ and $ch{i}^c(G)>t$. Let $m(k,x)$ denote the minimum number of hyperedges %in a $k$-uniform hypergraph $G$ such that some $k$-uniform hypergraph $G$ with $m(k,x)$ hyperedges does not have a bicoloring cover of size $x$. We show that $2^{(k-1)x-1}<m(k,x)leqxcdot{k}^{2}cdot{2}^{(k+1)x+2}$. Let the {it dependency $d(G)$} of $G$ be the maximum number of hyperedge neighbors of any hyperedge in $G$. We propose an algorithm for computing a bicoloring cover of size $x$ for $G$ if $d(G)leq(frac{2}^{x(k-1)}e-1)$ using $nx+kxfracmd$ random bits.

This page was built for publication: Bicoloring covers for graphs and hypergraphs

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