๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Improved bounds for the chromatic index of graphs and multigraphs

โœ Scribed by Hakimi, S. Louis; Schmeichel, Edward F.

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
321 KB
Volume
32
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

โœฆ Synopsis

We show that coloring the edges of a multigraph G in a particular order often leads to improved upper bounds for the chromatic index ฯ‡ (G). Applying this to simple graphs, we significantly generalize recent conditions based on the core of G (i.e., the subgraph of G induced by the vertices of degree โˆ†(G)), which insure that ฯ‡ (G) = โˆ†(G). Finally, we show that ฯ‡ (G) โ‰ค โˆ†(G) + ยต(G) in any multigraph G in which every cycle of length larger than 2 contains a simple edge, where ยต(G) is the largest edge multiplicity in G.

๐Ÿ“œ SIMILAR VOLUMES

The round-up property of the fractional
The round-up property of the fractional chromatic number for proper circular arc graphs
โœ Niessen, Thomas; Kind, Jaakob ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 131 KB ๐Ÿ‘ 1 views

Let G = (V, E) be a graph and let k be a nonnegative integer. A vector c โˆˆ Z V + is called k-colorable iff there exists a coloring of G with k colors that assigns exactly c(v) colors to vertex v โˆˆ V . Denote by ฯ‡(G) and ฯ‡ f (G) the chromatic number and fractional chromatic number, respectively. We p

Improved upper bounds for the reliabilit
Improved upper bounds for the reliability of d-dimensional consecutive-k-out-of-n : F systems
โœ Anant P. Godbole; Laura K. Potter; Jessica K. Sklar ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 82 KB ๐Ÿ‘ 1 views

Consider a 2-dimensional consecutive-k-out-of-n : F system, as described by Salvia and Lasher [9], whose components have independent, perhaps identical, failure probabilities. In this paper, we use Janson's exponential inequalities to derive improved upper bounds on such a system's reliability, and