✦ LIBER ✦

The chromatic index of multigraphs that are nearly full

✍ Scribed by Michael J. Plantholt; Shailesh K. Tipnis

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 610 KB
Volume: 82
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90325-c

No coin nor oath required. For personal study only.

✦ Synopsis

We summarize previous results on the chromatic index of nearly complete simple graphs. Hilton has shown how the first of these results generalizes to multigraphs. We give an extension of another of the simple graph results to a multigraph version.

📜 SIMILAR VOLUMES

The chromatic index of nearly bipartite

The chromatic index of nearly bipartite multigraphs

✍ Larry Eggan; Michael Plantholt 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 672 KB

Asymptotics of the Chromatic Index for M

Asymptotics of the Chromatic Index for Multigraphs

✍ Jeff Kahn 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 835 KB

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 predic

Asymptotics of the list-chromatic index

Asymptotics of the list-chromatic index for multigraphs

✍ Jeff Kahn 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB 👁 1 views

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

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

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