|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
On some upper bounds on the fractional chromatic number of weighted graphs | | Ashwin Ganesan
; | | Date: |
18 Jan 2010 | | Abstract: | Given a weighted graph $G_x$, where $(x(v): v in V)$ is a non-negative,
real-valued weight assigned to the vertices of G, let $B(G_x)$ be an upper
bound on the fractional chromatic number of the weighted graph $G_x$; so
$chi_f(G_x) le B(G_x)$. To investigate the worst-case performance of the
upper bound $B$, we study the graph invariant $$eta(G) = sup_{x
e 0}
frac{B(G_x)}{chi_f(G_x)}.$$
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. | | Source: | arXiv, 1001.3053 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER