✦ LIBER ✦

The chromatic index of complete multipartite graphs

✍ Scribed by D. G. Hoffman; C. A. Rodger

Publisher: John Wiley and Sons
Year: 1992
Tongue: English
Weight: 266 KB
Volume: 16
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190160207

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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

📜 SIMILAR VOLUMES

Fair Hamilton Decompositions of Complete

Fair Hamilton Decompositions of Complete Multipartite Graphs

✍ C.D. Leach; C.A. Rodger 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 88 KB

A fair hamilton decomposition of the complete multipartite graph G is a set of hamilton cycles in G whose edges partition the edges of G in such a way that, for each pair of parts and for each pair of hamilton cycles H 1 and H 2 , the difference in the number of edges in H 1 and H 2 joining vertices

Critical groups for complete multipartit

Critical groups for complete multipartite graphs and Cartesian products of complete graphs

✍ Brian Jacobson; Andrew Niedermaier; Victor Reiner 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB

## Abstract The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph, and which is closely related to the graph Laplacian. Its group structure has been determined for relatively few classes of graphs, e.g., complete graphs and compl

Factorizations of complete multipartite

Factorizations of complete multipartite graphs into generalized cubes

✍ El--Zanati, S.; Vanden Eynden, C. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB 👁 2 views

For a positive integer d, the usual d-dimensional cube Q d is defined to be the graph (K 2 ) d , the Cartesian product of d copies of K 2 . We define the generalized cube Q(K k , d) to be the graph (K k ) d for positive integers d and k. We investigate the decomposition of the complete multipartite

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

Maximal sets of hamilton cycles in compl

Maximal sets of hamilton cycles in complete multipartite graphs

✍ Mike Daven; J. A. MacDougall; C. A. Rodger 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB 👁 2 views

## Abstract A set __S__ of edge‐disjoint hamilton cycles in a graph __G__ is said to be __maximal__ if the edges in the hamilton cycles in __S__ induce a subgraph __H__ of __G__ such that __G__ − __E__(__H__) contains no hamilton cycles. In this context, the spectrum __S__(__G__) of a graph __G__ i

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}