✦ LIBER ✦

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

✍ Scribed by Ashwin Ganesan

Book ID: 104000853
Publisher: Elsevier Science
Year: 2010
Tongue: English
Weight: 214 KB
Volume: 23
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2010.02.001

No coin nor oath required. For personal study only.

✦ Synopsis

Given a weighted graph G x , where (x(v) : v ∈ 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 χ f (G x ) ≤ B(G x ). We consider a particular upper bound B resulting from a generalization of the greedy coloring algorithm to weighted graphs. To investigate the worst-case performance of this upper bound, we study the graph invariant

This graph invariant is shown to be equal to the size of the largest star subgraph in the graph. These results have implications for the design and performance of distributed communication networks.

📜 SIMILAR VOLUMES

An upper bound for the total chromatic n

An upper bound for the total chromatic number of dense graphs

✍ H. R. Hind 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 340 KB 👁 1 views

## Abstract In this paper we consider those graphs that have maximum degree at least 1/__k__ times their order, where __k__ is a (small) positive integer. A result of Hajnal and Szemerédi concerning equitable vertex‐colorings and an adaptation of the standard proof of Vizing's Theorem are used to s

On an upper bound for the harmonious chr

On an upper bound for the harmonious chromatic number of a graph

✍ Zhikang Lu 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph that has been given by Sin‐Min Lee and John Mitchem is improved.

An upper bound for the harmonious chroma

An upper bound for the harmonious chromatic number of a graph

✍ Sin-Min Lee; John Mitchem 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB 👁 2 views

An upper bound for the harmonious chromatic number of a graph G is given. Three corollaries of the theorem are theorems or improvements of the theorems of Miller and Pritikin. The assignment of colors to the vertices of a graph such that each vertex has exactly one color has been studied for well o

An upper bound on the chromatic number o

An upper bound on the chromatic number of a circle graph withoutK4

✍ G. V. Nenashev 📂 Article 📅 2012 🏛 Springer US 🌐 English ⚖ 227 KB

New upper bounds for the chromatic numbe

New upper bounds for the chromatic number of a graph

✍ Ladislav Stacho 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 55 KB 👁 3 views

The fractional chromatic number of infin

The fractional chromatic number of infinite graphs

✍ Imre Leader 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 398 KB 👁 1 views

## Abstract The fractional chromatic number of a graph __G__ is the infimum of the total weight that can be assigned to the independent sets of __G__ in such a way that, for each vertex __v__ of __G__, the sum of the weights of the independent sets containing __v__ is at least 1. In this note we g