๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An extension of bipartite multigraphs

โœ Scribed by D. De Werra

Publisher
Elsevier Science
Year
1976
Tongue
English
Weight
702 KB
Volume
14
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

Usual edge colorings have been generalized in various ways; we wilI consider here essentially good edge colorings as well as equitable edge colorings. It is known that bipartite multigraphs present the property of having an equitable k-coloring for each k 3 2. This implies that they also have a good k-coloring for each k 2 2. In this paper, we characterize a chss of multigraphs which may be considered as a genera'ization of bipar?ite multigraphs, in the sense that for each k 2 2 they have a good k-coloring. A more res?rictive class is derived where all multigraphs have an equitable k-coloring for each Ft > 2.

๐Ÿ“œ SIMILAR VOLUMES

The List Chromatic Index of a Bipartite
The List Chromatic Index of a Bipartite Multigraph
โœ F. Galvin ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 243 KB

For a bipartite multigraph, the list chromatic index is equal to the chromatic index (which is, of course, the same as the maximum degree). This generalizes Janssen's result on complete bipartite graphs \(K_{m, n}\) with \(m \neq n\); in the case of \(K_{n, n}\) it answers a question of Dinitz. (The

Applying a proof of tverberg to complete
Applying a proof of tverberg to complete bipartite decompositions of digraphs and multigraphs
โœ Dan Pritikin ๐Ÿ“‚ Article ๐Ÿ“… 1986 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 195 KB

Graham and Pollak 121 proved that n -1 is the minimum number of edge-disjoint complete bipartite subgraphs into which the edges of K,, decompose. Tverberg 161, using a linear algebraic technique, was the first to give a simple proof of this result. We apply Tverberg's technique to obtain results for

Extensions of some factorization results
Extensions of some factorization results from simple graphs to multigraphs
โœ El-Zanati, S. I.; Plantholt, M. J.; Tipnis, S. K. ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 71 KB

It was shown in a recent paper that an rs-regular multigraph G with maximum multiplicity ยต(G) โ‰ค r can be factored into r regular simple graphs if first we allow the deletion of a relatively small number of hamilton cycles from G. In this paper, we use this theorem to obtain extensions of some factor