✦ LIBER ✦

The chromatic index of nearly bipartite multigraphs

✍ Scribed by Larry Eggan; Michael Plantholt

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 672 KB
Volume: 40
Category: Article
ISSN: 0095-8956
DOI: 10.1016/0095-8956(86)90065-1

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

The chromatic index of multigraphs that

The chromatic index of multigraphs that are nearly full

✍ Michael J. Plantholt; Shailesh K. Tipnis 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 610 KB

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.

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

The total chromatic number of nearly com

The total chromatic number of nearly complete bipartite graphs

✍ A.J.W Hilton 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 753 KB

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