Thumbnail
Access Restriction
Open

Author Hook, Jonelle ♦ Isaak, Garth
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The graph Ramsey number R(G, H) is the smallest integer n such that every 2-coloring of the edges of Kn contains either a red copy of G or a blue copy of H. We find the largest star that can be removed from Kn such that the underlying graph is still forced to have a red G or a blue H. Thus, we introduce the star-avoiding Ramsey number r∗(G, H) as the smallest integer k such that every 2-coloring of the edges of Kn − K1,n−1−k contains either a red copy of G or a blue copy of H. We find the star-avoiding Ramsey number for trees versus complete graphs, multiple copies of K2 and K3, and paths versus a 4-cycle. In addition to finding the star-avoiding Ramsey numbers, the critical graphs are classified for R(Tn, Km), R(nK2, mK2) and R(Pn, C4).
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 2009-01-01