𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Chromatic-index critical multigraphs of order 20

✍ Scribed by Gr�newald, Stefan

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
243 KB
Volume
33
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Chromatic-index-critical graphs of even
Chromatic-index-critical graphs of even order
✍ Gr�newald, Stefan; Steffen, Eckhard 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 298 KB 👁 1 views

A k-critical (multi-) graph G has maximum degree k, chromatic index χ (G) = k + 1, and χ (G -e) < k + 1 for each edge e of G. For each k ≥ 3, we construct k-critical (multi-) graphs with certain properties to obtain counterexamples to some well-known conjectures.

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