✦ LIBER ✦

The chromatic index of graphs with a spanning star

✍ Scribed by Mike Plantholt

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

No coin nor oath required. For personal study only.

✦ Synopsis

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 conjectured that this condition is also sufficient. We present a proof of that conjecture and a corollary that helps determine the chromatic index of some graphs with 2s points and maximum degree 2s − 2.

📜 SIMILAR VOLUMES

The star chromatic number of a graph

✍ H. L. Abbott; B. Zhou 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 469 KB 👁 2 views

## Abstract We study a generalization of the notion of the chromatic number of a graph in which the colors assigned to adjacent vertices are required to be, in a certain sense, far apart. © 1993 John Wiley & Sons, Inc.

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.

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

The star-chromatic number of planar grap

The star-chromatic number of planar graphs

✍ Moser, David 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 2 views

The star-chromatic number of a graph, a parameter introduced by Vince, is a natural generalization of the chromatic number of a graph. Here we construct planar graphs with star-chromatic number r, where r is any rational number between 2 and 3, partially answering a question of Vince.

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

On the oriented chromatic index of orien

On the oriented chromatic index of oriented graphs

✍ Pascal Ochem; Alexandre Pinlou; Éric Sopena 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB

## Abstract A homomorphism from an oriented graph __G__ to an oriented graph __H__ is a mapping $\varphi$ from the set of vertices of __G__ to the set of vertices of __H__ such that $\buildrel {\longrightarrow}\over {\varphi (u) \varphi (v)}$ is an arc in __H__ whenever $\buildrel {\longrightarrow}