The performance of an upper bound on the fractional chromatic number of weighted graphs

DOI10.1016/J.AML.2010.02.001MaRDI QIDQ968556zbMATH OpenOpenAlexFDO

Authors Ashwin Ganesan

Publication date 5 May 2010

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.3053

zbMATH Keywords

distributed systemsupper boundweighted graphworst-case performancefractional chromatic numbergreedy coloring algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Abstract: Given a weighted graph $$, where $(x(v):vinV)$ is a non-negative, real-valued weight assigned to the vertices of G, let $$ be an upper bound on the fractional chromatic number of the weighted graph $$; so $$. To investigate the worst-case performance of the upper bound $B$, we study the graph invariant ${\displaystyle }$�eta(G) = sup_{�x

e 0} frac{B(G_�x)}{chi_f(G_�x)}.${\displaystyle }$

oindent 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.

Recommendations

• New lower bounds on the weighted chromatic number of a graph
• Max-coloring of vertex-weighted graphs
• Generalized edge-colorings of weighted graphs
• Edge-colorings of weighted graphs (extended abstract)
• scientific article; zbMATH DE number 4144006

Cites work

• Graph imperfection. I
• Link scheduling in polynomial time
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(1)

• Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model

This page was built for publication: The performance of an upper bound on the fractional chromatic number of weighted graphs

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