✦ LIBER ✦

Homomorphisms to oriented cycles

✍ Scribed by Pavol Hell; Huishan Zhou; Xuding Zhu

Publisher: Springer-Verlag
Year: 1993
Tongue: English
Weight: 807 KB
Volume: 13
Category: Article
ISSN: 0209-9683
DOI: 10.1007/bf01303514

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

Homomorphisms to oriented paths

✍ Pavol Hell; Xuding Zhu 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 523 KB

Minimum Cost Homomorphism Dichotomy for

Minimum Cost Homomorphism Dichotomy for Oriented Cycles

✍ Gregory Gutin; Arash Rafiey; Anders Yeo 📂 Article 📅 2009 🏛 Springer Japan 🌐 English ⚖ 179 KB

On homomorphisms to edge-coloured cycles

✍ Richard C Brewster; Pavol Hell 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 184 KB

Homomorphisms of graphs into odd cycles

✍ A. M. H. Gerards 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 474 KB

Regular Graphs with No Homomorphisms ont

Regular Graphs with No Homomorphisms onto Cycles

✍ I.M. Wanless; N.C. Wormald 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 97 KB

We prove the existence of d-regular graphs with arbitrarily large girth and no homomorphism onto the cycle C s , where (d, s)=(3, 9) and (4, 5).