𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Anti-Ramsey numbers of doubly edge-critical graphs

✍ Scribed by Tao Jiang; Oleg Pikhurko

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
114 KB
Volume
61
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 among other things, determined this function for cliques. In general, few exact values of AR(n, H) are known. Let us call a graph H doubly edge‐critical if χ(H−e)≥p+ 1 for each edge e∈E(H) and there exist two edges e~1~, e~2~ of H for which χ(H−e~1~−e~2~)=p. Here, we obtain the exact value of AR(n, H) for any doubly edge‐critical H when n⩾n~0~(H) is sufficiently large. A main ingredient of our proof is the stability theorem of Erdős and Simonovits for the Turán problem. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 210–218, 2009

📜 SIMILAR VOLUMES

Anti-Ramsey Numbers of Subdivided Graphs
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

Constrained Ramsey numbers of graphs
Constrained Ramsey numbers of graphs
✍ Robert E. Jamison; Tao Jiang; Alan C. H. Ling 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## Abstract Given two graphs __G__ and __H__, let __f__(__G__,__H__) denote the minimum integer __n__ such that in every coloring of the edges of __K__~__n__~, there is either a copy of __G__ with all edges having the same color or a copy of __H__ with all edges having different colors. We show tha

Linear Ramsey numbers of sparse graphs
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

The independence number of an edge-chrom
The independence number of an edge-chromatic critical graph
✍ Douglas R. Woodall 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 77 KB 👁 1 views

A graph G with maximum degree and edge chromatic number (G)> is edge--critical if (G -e) = for every edge e of G. It is proved here that the vertex independence number of an edge--critical graph of order n is less than 3 5 n. For large , this improves on the best bound previously known, which was ro

Bipartite anti-Ramsey numbers of cycles
Bipartite anti-Ramsey numbers of cycles
✍ Maria Axenovich; Tao Jiang; André Kündgen 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 265 KB

## Abstract We determine the maximum number of colors in a coloring of the edges of __K~m,n~__ such that every cycle of length 2__k__ contains at least two edges of the same color. One of our main tools is a result on generalized path covers in balanced bipartite graphs. For positive integers __q__