✦ LIBER ✦

Vertex-splitting and chromatic index critical graphs

✍ Scribed by A.J.W. Hilton; C. Zhao

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 477 KB
Volume: 76
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(96)00125-4

No coin nor oath required. For personal study only.

✦ Synopsis

We study graphs which are critical with respect to the chromatic index. We relate these to the Overfull Conjecture and we study in particular their construction from regular graphs by subdividing an edge or by splitting a vertex.

📜 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 graphs of order

Chromatic index critical graphs of order 9

✍ Amanda G. Chetwynd; H.P. Yap 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 954 KB

We prove that a 2-connected graph of order 9 having maximum valency A 34 is chromatic index critical if and only if its valency-list is one of the following: 248, 3247 (except one graph), 258, 345 ', 4356, 26a, 356', 4267, 45266, 5465, 27', 367', 457', 46276, 52676, 56375, 6574, 57385, 6386, 627285,

Chromatic-Index-Critical Graphs of Order

Chromatic-Index-Critical Graphs of Orders 11 and 12

✍ G Brinkmann; E Steffen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 177 KB

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 tha

Vertex domination-critical graphs

✍ Jason Fulman; Denis Hanson; Gary Macgillivray 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 293 KB

Vertex domination-critical graphs

✍ Robert C. Brigham; Phyllis Z. Chinn; Ronald D. Dutton 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 303 KB