✦ LIBER ✦

Sparse Anti-Ramsey Graphs

✍ Scribed by Y. Kohayakawa; T. Luczak

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 269 KB
Volume: 63
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1995.1010

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that for every (l \geqslant 3) there exists a graph (G) of girth / such that in any proper edge-colouring of (G) one may find a cycle of length / all of whose edges are given different colours. 1995 Academic Press. Inc.

📜 SIMILAR VOLUMES

Linear Ramsey numbers of sparse graphs

✍ Lingsheng Shi 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

## Abstract The Ramsey number __R__(__G__~1~,__G__~2~) of two graphs __G__~1~ and __G__~2~ is the least integer __p__ so that either a graph __G__ of order __p__ contains a copy of __G__~1~ or its complement __G__^c^ contains a copy of __G__~2~. In 1973, Burr and Erdős offered a total of $25 for se

Anti-Ramsey Numbers of Subdivided Graphs

✍ Tao Jiang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 88 KB

Given a positive integer n and a family F of graphs, the anti-Ramsey number f(n, F) is the maximum number of colors in an edge-coloring of K n such that no subgraph of K n belonging to F has distinct colors on its edges. The Tura ´n number ex(n, F) is the maximum number of edges of an n-vertex graph

Anti-Ramsey numbers of doubly edge-criti

Anti-Ramsey numbers of doubly edge-critical graphs

✍ Tao Jiang; Oleg Pikhurko 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

## Abstract Given a graph __H__ and a positive integer __n__, __Anti‐Ramsey number AR__(__n, H__) is the maximum number of colors in an edge‐coloring of __K__~__n__~ that contains no polychromatic copy of __H__. The anti‐Ramsey numbers were introduced in the 1970s by Erdős, Simonovits, and Sós, who

Independence numbers of locally sparse g

Independence numbers of locally sparse graphs and a Ramsey type problem

✍ Noga Alon 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 409 KB 👁 1 views

Let G = (V, E ) be a graph on n vertices with average degree t 2 1 in which for every vertex u E V the induced subgraph on the set of all neighbors of u is r-colorable. We show that the independence number of G is at least log t , for some absolute positive constant c. This strengthens a well-known

Bisecting sparse random graphs

✍ Malwina J. Luczak; Colin McDiarmid 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB 👁 1 views

Girth of sparse graphs

✍ Béla Bollobás; Endre Szemerédi 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 73 KB

## Abstract For each fixed __k__ ≥ 0, we give an upper bound for the girth of a graph of order __n__ and size __n__ + __k__. This bound is likely to be essentially best possible as __n__ → ∞. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 194–200, 2002; DOI 10.1002/jgt.10023