𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Colouring Partial Joins of a Complete Graph and a Cycle

✍ Scribed by M. Stiebitz; W. Wessel

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
493 KB
Volume
163
Category
Article
ISSN
0025-584X

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Define the partial join of two graphs to be some graph arising from their disjoint union by adding a set of new edges each joining a vertex of the first graph and a vertex of the second one. We characterize all colour‐critical graphs being partial joins of a complete graph and an odd cycle thus completely answering a special case of a question raised by T. GALLAI in 1969.

πŸ“œ SIMILAR VOLUMES

A Note on Alternating Cycles in Edge-Col
A Note on Alternating Cycles in Edge-Coloured Graphs
✍ Anders Yeo πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 431 KB

Grossman and Ha ggkvist gave a sufficient condition under which a two-edgecoloured graph must have an alternating cycle (i.e., a cycle in which no two consecutive edges have the same colour). We extend their result to edge-coloured graphs with any number of colours. That is, we show that if there is

On cycle bases of a graph
On cycle bases of a graph
✍ M. M. SysΕ‚o πŸ“‚ Article πŸ“… 1979 πŸ› John Wiley and Sons 🌐 English βš– 358 KB
On the cycle polytope of a directed grap
On the cycle polytope of a directed graph
✍ Egon Balas; Maarten Oosten πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 185 KB πŸ‘ 2 views
A note on path and cycle decompositions
A note on path and cycle decompositions of graphs
✍ Dom Decaen πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 137 KB πŸ‘ 1 views

## Abstract In the study of decompositions of graphs into paths and cycles, the following questions have arisen: Is it true that every graph __G__ has a smallest path (resp. path‐cycle) decomposition __P__ such that every odd vertex of __G__ is the endpoint of exactly one path of __P__? This note g

Symmetric Hamilton cycle decompositions
Symmetric Hamilton cycle decompositions of complete graphs minus a 1-factor
✍ Richard A. Brualdi; Michael W. Schroeder πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 190 KB πŸ‘ 1 views

Let n β‰₯ 2 be an integer. The complete graph K n with a 1-factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K n -F has a decomposition into Hamilton cycles which are symmetric with respect to the 1-factor F if and only if n ≑ 2,4 mod 8. We also show that