✦ LIBER ✦

Homomorphisms of graphs into odd cycles

✍ Scribed by A. M. H. Gerards

Publisher: John Wiley and Sons
Year: 1988
Tongue: English
Weight: 474 KB
Volume: 12
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190120108

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Decomposing complete equipartite graphs

Decomposing complete equipartite graphs into odd square-length cycles: number of parts odd

✍ Benjamin R. Smith 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract In this article, we introduce a new technique for obtaining cycle decompositions of complete equipartite graphs from cycle decompositions of related multigraphs. We use this technique to prove that if __n__, __m__ and λ are positive integers with __n__ ≥ 3, λ≥ 3 and __n__ and λ both odd

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).

On Random Graph Homomorphisms into Z

✍ Itai Benjamini; Olle Häggström; Elchanan Mossel 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 319 KB

Given a bipartite connected finite graph G=(V, E) and a vertex v 0 # V, we consider a uniform probability measure on the set of graph homomorphisms f : V Ä Z satisfying f (v 0 )=0. This measure can be viewed as a G-indexed random walk on Z, generalizing both the usual time-indexed random walk and tr

Vertex colorings of graphs without short

Vertex colorings of graphs without short odd cycles

✍ Andrzej Dudek; Reshma Ramadurai 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 1 views

Motivated by the work of Nešetřil and R ödl on "Partitions of vertices" we are interested in obtaining some quantitative extensions of their result. In particular, given a natural number r and a graph G of order m with odd girth g, we show the existence of a graph H with odd girth at least g and ord

Short odd cycles in 4-chromatic graphs

✍ Nilli, A. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB 👁 3 views

It is shown that any 4-chromatic graph on n vertices contains an odd cycle of length smaller than √ 8n.

Small odd cycles in 4-chromatic graphs

✍ Tao Jiang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 50 KB

## Abstract It is shown that every 4‐chromatic graph on __n__ vertices contains an odd cycle of length less than $2\sqrt {n}\,+3$. This improves the previous bound given by Nilli [J Graph Theory 3 (1999), 145–147]. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 115–117, 2001