✦ LIBER ✦

The chromatic index of graphs of even order with many edges

✍ Scribed by A. G. Chetwynd; A. J. W. Hilton

Publisher: John Wiley and Sons
Year: 1984
Tongue: English
Weight: 313 KB
Volume: 8
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190080403

No coin nor oath required. For personal study only.

✦ Synopsis

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 Plantholt.

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

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

The chromatic index of graphs with a spa

The chromatic index of graphs with a spanning star

✍ Mike Plantholt 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 468 KB 👁 1 views

## Abstract Vizing's Theorem states that any graph __G__ has chromatic index either the maximum degree Δ(__G__) or Δ(__G__) + 1. If __G__ has 2~s~ + 1 points and Δ(__G__) = 2s, a well‐known necessary condition for the chromatic index to equal 2~s~ is that __G__ have at most 2s^2^ lines. Hilton conj

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.

On the Size of Edge Chromatic Critical G

On the Size of Edge Chromatic Critical Graphs

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 85 KB

In this paper, by applying the discharging method, we prove that if

The size of edge chromatic critical grap

The size of edge chromatic critical graphs with maximum degree 6

✍ Rong Luo; Lianying Miao; Yue Zhao 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 216 KB 👁 1 views

## Abstract In 1968, Vizing [Uaspekhi Mat Nauk 23 (1968) 117–134; Russian Math Surveys 23 (1968), 125–142] conjectured that for any edge chromatic critical graph ${{G}} = ({{V}}, {{E}})$ with maximum degree $\Delta$, $|{{E}}| \geq {{{1}}\over {{2}}}\{(\Delta {{- 1}})|{{V}}| + {{3}}\}$. This conject