2
$\begingroup$

Let $G=(V,E)$ be a simple graph. Let $w$ be a non-negative, integer valued weight function on the vertex set. The chromatic number $\chi(G,w)$ of the vertex-weighted graph $(G,w)$ is defined to be the minimum number of colors needed so that each vertex $v$ is assigned $w(v)$ colors and the color sets assigned to adjacent vertices are disjoint. By generalizing the well-known greedy coloring algorithm to weighted graphs, one obtains the upper bound $\chi(G,w) \le \max_{v \in V} \{w(v)+w(N(v))\}$, where $w(N(v))$ denotes the sum of the weights of the vertices that are neighbors of $v$.

What is a similar upper bound for the weighted chromatic number of a hypergraph? Any results or pointers to the literature would be helpful.

The definition of the chromatic number of a weighted hypergraph is as follows. Let $H=(V, \mathcal{E})$ be a hypergraph with ground set $V$ and a set $\mathcal{E}$ of hyperedges. A proper coloring of the hypergraph is an assignment of a color to each vertex such that no hyperedge is monochromatic. This is generalized to weighted hypergraphs as follows. Let $w$ be a non-negative, integer valued weight function on $V$. The chromatic number $\chi(H,w)$ is the minimum number of colors needed so that each vertex $v$ is assigned $w(v)$ colors and no color class contains a hyperedge.

$\endgroup$
  • $\begingroup$ In the graph case, you may replace each vertex $v$ by $w(v)$ vertices connected to each neighbor of $v$ as well as to each other. The weighted chromatic number of the initial graph equals the chromatic number of the obtained one. Now you are free to apply any result on the usual chromatic numbers. The situation with hypergraphs is completely analogous. $\endgroup$ – Ilya Bogdanov Apr 3 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.