𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Chromatic-index-critical graphs of even order

✍ Scribed by Gr�newald, Stefan; Steffen, Eckhard

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
298 KB
Volume
30
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

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.

Strong chromatic index of subset graphs
Strong chromatic index of subset graphs
✍ Quinn, Jennifer J.; Benjamin, Arthur T. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 2 views

The strong chromatic index of a graph G, denoted sq(G), is the minimum number of parts needed to partition the edges of G into induced matchings. For 0 ≤ k ≤ l ≤ m, the subset graph S m (k, l) is a bipartite graph whose vertices are the kand l-subsets of an m element ground set where two vertices ar

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