𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On even factorizations and the chromatic index of the Kautz and de Bruijn digraphs

✍ Scribed by Jean-Claude Bermond Cnrs; Pavol Hell

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
484 KB
Volume
17
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Motivated by the problem of designing large packet radio networks, we show that the Kautz and de Bruijn digraphs with in‐ and outdegree d have arc‐chromatic index 2d. In order to do this, we introduce the concept of even 1‐factorizations. An even 1‐factor of a digraph is a spanning subgraph consisting of vertex disjoint loops and even cycles; an even 1‐factorization is a partition of the arcs into even 1‐factors. We prove that if a digraph admits an even 1‐factorization, then so does its line digraph. (In fact, we show that the line digraph admits an even 1‐factorization even under a weaker assumption discussed below.) As a consequence, we derive the above property of the Kautz and de Bruijn digraphs relevant to packet radio networks. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

The Spectrum of de Bruijn and Kautz Grap
The Spectrum of de Bruijn and Kautz Graphs
✍ C. Delorme; J.-P. Tillich 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 187 KB

We give here a complete description of the spectrum of de Bruijn and Kautz graphs. It is well known that spectral techniques have proved to be very useful tools to study graphs, and we give some examples of application of our result, by deriving tight bounds on the expansion parameters of those grap

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

A note on the line-distinguishing chroma
A note on the line-distinguishing chromatic number and the chromatic index of a graph
✍ N. Zagaglia Salvi 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

## Abstract Let λ(__G__) be the line‐distinguishing chromatic number and __x__′(__G__) the chromatic index of a graph __G__. We prove the relation λ(__G__) ≥ __x__′(__G__), conjectured by Harary and Plantholt. © 1993 John Wiley & Sons, Inc.

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}

On the Degree, Size, and Chromatic Index
On the Degree, Size, and Chromatic Index of a Uniform Hypergraph
✍ Noga Alon; Jeong Han Kim 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 274 KB

Let H be a k-uniform hypergraph in which no two edges share more than t common vertices, and let D denote the maximum degree of a vertex of H. We conjecture that for every =>0, if D is sufficiently large as a function of t, k, and =, then the chromatic index of H is at most (t&1+1Ât+=) D. We prove t