✦ LIBER ✦

Chromatic-Index-Critical Graphs of Orders 11 and 12

✍ Scribed by G Brinkmann; E Steffen

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 177 KB
Volume: 19
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1998.0254

No coin nor oath required. For personal study only.

✦ Synopsis

A chromatic-index-critical graph G on n vertices is non-trivial if it has at most n 2 edges. We prove that there is no chromatic-index-critical graph of order 12, and that there are precisely two non-trivial chromatic-index-critical graphs on 11 vertices. Together with known results this implies that there are precisely three non-trivial chromatic-index-critical graphs of order ≤ 12.

📜 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 👁 2 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.

A construction of chromatic index critic

A construction of chromatic index critical graphs

✍ Hian Poh Yap 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

## Abstract We prove that if __K__ is an undirected, simple, connected graph of even order which is of class one, regular of degree __p__ ≥ 2 and such that the subgraph induced by any three vertices is either connected or null, then any graph __G__ obtained from __K__ by splitting any vertex is __p

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.

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

The chromatic index of graphs of even or

The chromatic index of graphs of even order with many edges

✍ A. G. Chetwynd; A. J. W. Hilton 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 313 KB

We show that, for r = 1, 2, a graph G with 2n + 2 (26) vertices and maximum degree 2n + 1 -r is of Class 2 if and only if (E(G\v)I > ('"2+')m, where v is a vertex of G of minimum degree, and we make a conjecture for 1 s r s n, of which this result is a special case. For r = 1 this result is due to P

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