Abstract | ||
---|---|---|
The graph Ramsey numberR(G,H) is the smallest integer r such that every 2-coloring of the edges of K"r contains either a red copy of G or a blue copy of H. We find the largest star that can be removed from K"r such that the underlying graph is still forced to have a red G or a blue H. Thus, we introduce the star-critical Ramsey numberr"*(G,H) as the smallest integer k such that every 2-coloring of the edges of K"r-K"1","r"-"1"-"k contains either a red copy of G or a blue copy of H. We find the star-critical Ramsey number for trees versus complete graphs, multiple copies of K"2 and K"3, and paths versus a 4-cycle. In addition to finding the star-critical Ramsey numbers, the critical graphs are classified for R(T"n,K"m), R(nK"2,mK"2) and R(P"n,C"4). |
Year | DOI | Venue |
---|---|---|
2011 | 10.1016/j.dam.2010.11.007 | Discrete Applied Mathematics |
Keywords | Field | DocType |
complete graph,red g,blue h.,critical graph,multiple copy,star-critical ramsey number,graph ramsey numberr,smallest integer r,graph ramsey number,red copy,star-critical ramsey numberr,blue copy,ramsey number | Integer,Complete graph,Discrete mathematics,Graph,Combinatorics,Tree (graph theory),Ramsey's theorem,Critical graph,Mathematics | Journal |
Volume | Issue | ISSN |
159 | 5 | Discrete Applied Mathematics |
Citations | PageRank | References |
8 | 0.83 | 2 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jonelle Hook | 1 | 8 | 1.51 |
Garth Isaak | 2 | 172 | 24.01 |