✦ LIBER ✦

A construction of chromatic index critical graphs

✍ Scribed by Hian Poh Yap

Publisher: John Wiley and Sons
Year: 1981
Tongue: English
Weight: 219 KB
Volume: 5
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190050205

No coin nor oath required. For personal study only.

✦ Synopsis

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‐critical. We find that various constructions of critical graphs by S. Fiorini are special cases of a corollary of this result.

📜 SIMILAR VOLUMES

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

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.

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

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

The chromatic index of complete multipar

The chromatic index of complete multipartite graphs

✍ D. G. Hoffman; C. A. Rodger 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB

## Abstract We show that a complete multipartite graph is class one if and only if it is not eoverfull, thus determining its chromatic index.

Game chromatic index of k-degenerate gra

Game chromatic index of k-degenerate graphs

✍ Leizhen Cai; Xuding Zhu 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB 👁 1 views