# Critical Graphs for R(P n , P m ) and the Star-Critical Ramsey Number for Paths

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 4, page 689-701
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJonelle Hook. " Critical Graphs for R(P n , P m ) and the Star-Critical Ramsey Number for Paths ." Discussiones Mathematicae Graph Theory 35.4 (2015): 689-701. <http://eudml.org/doc/275867>.

@article{JonelleHook2015,

abstract = {The graph Ramsey number R(G,H) is the smallest integer r such that every 2-coloring of the edges of Kr contains either a red copy of G or a blue copy of H. The star-critical Ramsey number r∗(G,H) is the smallest integer k such that every 2-coloring of the edges of Kr − K1,r−1−k contains either a red copy of G or a blue copy of H. We will classify the critical graphs, 2-colorings of the complete graph on R(G,H) − 1 vertices with no red G or blue H, for the path-path Ramsey number. This classification will be used in the proof of r∗(Pn, Pm).},

author = {Jonelle Hook},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {Ramsey number; critical graph; star-critical Ramsey number; path},

language = {eng},

number = {4},

pages = {689-701},

title = { Critical Graphs for R(P n , P m ) and the Star-Critical Ramsey Number for Paths },

url = {http://eudml.org/doc/275867},

volume = {35},

year = {2015},

}

TY - JOUR

AU - Jonelle Hook

TI - Critical Graphs for R(P n , P m ) and the Star-Critical Ramsey Number for Paths

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 4

SP - 689

EP - 701

AB - The graph Ramsey number R(G,H) is the smallest integer r such that every 2-coloring of the edges of Kr contains either a red copy of G or a blue copy of H. The star-critical Ramsey number r∗(G,H) is the smallest integer k such that every 2-coloring of the edges of Kr − K1,r−1−k contains either a red copy of G or a blue copy of H. We will classify the critical graphs, 2-colorings of the complete graph on R(G,H) − 1 vertices with no red G or blue H, for the path-path Ramsey number. This classification will be used in the proof of r∗(Pn, Pm).

LA - eng

KW - Ramsey number; critical graph; star-critical Ramsey number; path

UR - http://eudml.org/doc/275867

ER -

## References

top- [1] L. Gerencsér and A. Gyárfás, On Ramsey-type problems, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 10 (1967) 167-170. Zbl0163.45502
- [2] J. Hook, The classification of critical graphs and star-critical Ramsey numbers (Ph.D. Thesis, Lehigh University, 2010).
- [3] J. Hook and G. Isaak, Star-critical Ramsey numbers, Discrete Appl. Math. 159 (2011) 328-334. doi:10.1016/j.dam.2010.11.007[Crossref] Zbl1207.05212
- [4] R.J. Faudree, S.L. Lawrence, T.D. Parsons and R.H. Schelp, Path-cycle Ramsey numbers, Discrete Math. 10 (1974) 269-277. doi:10.1016/0012-365X(74)90122-8 Zbl0293.05120
- [5] R.J. Faudree and R.H. Schelp, All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974) 313-329. doi:10.1016/0012-365X(74)90151-4 Zbl0294.05122
- [6] D.B. West, Introduction to Graph Theory (Second Ed., Prentice Hall, Upper Saddle River, New Jersey, 2000).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.