On some upper bounds on the fractional chromatic number of weighted graphs

Details On some upper bounds on the fractional chromatic number of weighted graphs On some upper bounds on the fractional chromatic number of weighted graphs

2010-01-18

arxiv.org/abs/1001.3053v4

Computer Science

Information Theory

Scientific paper

Given a weighted graph $G_\bx$, where $(x(v): v \in V)$ is a non-negative, real-valued weight assigned to the vertices of G, let $B(G_\bx)$ be an upper bound on the fractional chromatic number of the weighted graph $G_\bx$; so $\chi_f(G_\bx) \le B(G_\bx)$. To investigate the worst-case performance of the upper bound $B$, we study the graph invariant $$\beta(G) = \sup_{\bx \ne 0} \frac{B(G_\bx)}{\chi_f(G_\bx)}.$$ \noindent This invariant is examined for various upper bounds $B$ on the fractional chromatic number. In some important cases, this graph invariant is shown to be related to the size of the largest star subgraph in the graph. This problem arises in the area of resource estimation in distributed systems and wireless networks; the results presented here have implications on the design and performance of decentralized communication networks.

Affiliated with

Also associated with

No associations

Rating

On some upper bounds on the fractional chromatic number of weighted graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On some upper bounds on the fractional chromatic number of weighted graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On some upper bounds on the fractional chromatic number of weighted graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-661299