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

DOI10.1016/J.AML.2010.02.001zbMATH Open1215.05064arXiv1001.3053OpenAlexW1981855427MaRDI QIDQ968556FDOQ968556

Authors: Ashwin Ganesan 

Publication date: 5 May 2010

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

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.

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

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

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)

Cites Work

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

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)