𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On homomorphisms to edge-coloured cycles

✍ Scribed by Richard C Brewster; Pavol Hell

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
184 KB
Volume
5
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

πŸ“œ 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

Homomorphisms to oriented cycles
Homomorphisms to oriented cycles
✍ Pavol Hell; Huishan Zhou; Xuding Zhu πŸ“‚ Article πŸ“… 1993 πŸ› Springer-Verlag 🌐 English βš– 807 KB
A Polynomial Algorithm for Homomorphisms
A Polynomial Algorithm for Homomorphisms to Oriented Cycles
✍ X.D. Zhu πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 559 KB

W. Gutjahr, E. Welzl, and G. Woeginger have given a polynomial time algorithm to decide whether a given digraph is homomorphic to an oriented path. The corresponding problem for oriented cycles (i.e., given a digraph \(G\), is it homomorphic to a fixed oriented cycle \(C\) ?) remained open. We prove