✦ LIBER ✦

The List Chromatic Index of a Bipartite Multigraph

✍ Scribed by F. Galvin

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 243 KB
Volume: 63
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1995.1011

No coin nor oath required. For personal study only.

✦ Synopsis

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 list chromatic index of a multigraph is the least number (n) for which the edges can be colored so that adjacent edges get different colors, the color of each edge being chosen from an arbitrarily prescribed list of (n) different colors associated with that edge.) 1995 Academic Press, Inc.

📜 SIMILAR VOLUMES

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

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.

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

The edge chromatic number of a directed/

The edge chromatic number of a directed/mixed multigraph

✍ Mel'nikov, Leonid S.; Vizing, Vadim G. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB 👁 2 views

We consider colorings of the directed and undirected edges of a mixed multigraph G by an ordered set of colors. We color each undirected edge in one color and each directed edge in two colors, such that the color of the first half of a directed edge is smaller than the color of the second half. The

A generalized construction of chromatic

A generalized construction of chromatic index critical graphs from bipartite graphs

✍ Michael Plantholt 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 378 KB

W e prove that any graph with maximum degree n which can be obtained by removing exactly 2n -1 edges from the join K? -K, ,, is n-critical This generalizes special constructions of critical graphs by S Fiorini and H P Yap, and suggests a possible extension of another general construction due to Yap