✦ LIBER ✦

A note concerning the chromatic index of multigraphs

✍ Scribed by A. J. W. Hilton; Bill Jackson

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 214 KB
Volume: 11
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190110302

No coin nor oath required. For personal study only.

✦ Synopsis

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 graphs due to Vizing and to Chetwynd and Hilton.

📜 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

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

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

A note on the line-distinguishing chroma

A note on the line-distinguishing chromatic number and the chromatic index of a graph

✍ N. Zagaglia Salvi 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

## Abstract Let λ(__G__) be the line‐distinguishing chromatic number and __x__′(__G__) the chromatic index of a graph __G__. We prove the relation λ(__G__) ≥ __x__′(__G__), conjectured by Harary and Plantholt. © 1993 John Wiley & Sons, Inc.

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