𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Vertex coverings by monochromatic paths and cycles

✍ Scribed by A. Gyárfás

Publisher
John Wiley and Sons
Year
1983
Tongue
English
Weight
254 KB
Volume
7
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

We survey some results on covering the vertices of 2-colored complete graphs by t w o paths or by t w o cycles Qf different color. W e show the role of these results i n determining path Ramsey numbers and in algorithms for finding long monochromatic paths or cycles in 2-colored complete graphs.

If c(xI

X ~, X ~+ ~ ) thenpi+, = x l , x 2 , . . . ,xi,xi+l. Stop. Ifc(xi+,&,) = c(xl,x2) thenPi+l =

📜 SIMILAR VOLUMES

Double coverings of 2-paths by Hamilton
Double coverings of 2-paths by Hamilton cycles*
✍ Midori Kobayashi; Nobuaki Mutoh; Kiyasu-Zen'iti; Gisaku Nakamura 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB

## Abstract A double Dudeney set in __K~n~__ is a multiset of Hamilton cycles in __K~n~__ having the property that each 2‐path in __K~n~__ lies in exactly two of the cycles. A double Dudeney set in __K~n~__ has been constructed when __n__ ≥ 4 is even. In this paper, we construct a double Dudeney se

Multiple vertex coverings by cliques
Multiple vertex coverings by cliques
✍ Wayne Goddard; Michael A. Henning 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB

For positive integers m 1 ; . . . ; m k , let f (m 1 ; . . . ; m k ) be the minimum order of a graph whose edges can be colored with k colors such that every vertex is in a clique of cardinality m i , all of whose edges have the ith color for all i ¼ 1; 2; . . . ; k. The value for k ¼ 2 was determin

Small cycle double covers of products I:
Small cycle double covers of products I: Lexicographic product with paths and cycles
✍ R. J. Nowakowski; K. Seyffarth 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB

## Abstract Bondy conjectured that every simple bridgeless graph has a small cycle double cover (SCDC). We show that this is the case for the lexicographic products of certain graphs and along the way for the Cartesian product as well. Specifically, if __G__ does not have an isolated vertex then __

Degree sums and graphs that are not cove
Degree sums and graphs that are not covered by two cycles
✍ Saito, Akira 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 2 views

For a graph G, let σ 3 (G) = min{deg G x + deg G y + deg G z: {x, y, z} is an independent set in G}. Enomoto et al. [Enowoto et al., J Graph Theory 20 (1995), 419-422] have proved that the vertex set of a 2-connected graph G of order n with σ 3 (G) ≥ n is covered by two cycles, edges or vertices. Ex