𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Asymptotics of the Chromatic Index for Multigraphs

✍ Scribed by Jeff Kahn

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
835 KB
Volume
68
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

For a multigraph G, let D(G) denote maximum degree and set

We show that the chromatic index /$(G) is asymptotically max[D(G), 1(G)]. The latter is, by a theorem of Edmonds (1965), the fractional chromatic index of G, and the asymptotics established here are part of a conjecture of the author predicting similar agreement of fractional and ordinary chromatic indices for more general hypergraphs. Of particular interest in the present proof is the use of probabilistic ideas and ``hard-core'' distributions to go from fractional to ordinary (integer) colorings.

πŸ“œ SIMILAR VOLUMES

A note concerning the chromatic index of
A note concerning the chromatic index of multigraphs
✍ A. J. W. Hilton; Bill Jackson πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 214 KB

We improve an upper bound for the chromatic index of a multigraph due to Andersen and Gol'dberg. As a corollary w e deduce that if no t w o edges of multiplicity at least t w o in G are adjacent, then ,y'(G) s A ( G ) + 1. In addition w e generalize results concerning the structure of critical graph

Improved bounds for the chromatic index
Improved bounds for the chromatic index of graphs and multigraphs
✍ Hakimi, S. Louis; Schmeichel, Edward F. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 321 KB πŸ‘ 2 views

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

Chromatic-index critical multigraphs of
Chromatic-index critical multigraphs of order 20
✍ GrοΏ½newald, Stefan πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 243 KB πŸ‘ 1 views

The weak critical graph conjecture [1,7] claims that there exists a constant c > 0 such that every critical multigraph M with at most c β€’ βˆ†(M ) vertices has odd order. We disprove this conjecture by constructing critical multigraphs of order 20 with maximum degree k for all k β‰₯ 5.

The List Chromatic Index of a Bipartite
The List Chromatic Index of a Bipartite Multigraph
✍ F. Galvin πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 243 KB

For a bipartite multigraph, the list chromatic index is equal to the chromatic index (which is, of course, the same as the maximum degree). This generalizes Janssen's result on complete bipartite graphs \(K_{m, n}\) with \(m \neq n\); in the case of \(K_{n, n}\) it answers a question of Dinitz. (The