Loading...
Please wait, while we are loading the content...
Similar Documents
Degree Ramsey Numbers of Graphs
| Content Provider | Scilit |
|---|---|
| Author | Kinnersley, William B. Milans, Kevin G. West, Douglas B. |
| Copyright Year | 2012 |
| Description | Let H G mean that every s-colouring of E(H) produces a monochromatic copy of G in some colour class. Let the s-colour degree Ramsey number of a graph G, written $R_{Δ}$(G; s), be min{Δ(H): H G}. If T is a tree in which one vertex has degree at most k and all others have degree at most ⌈k/2⌉, then $R_{Δ}$(T; s) = s(k − 1) + ϵ, where ϵ = 1 when k is odd and ϵ = 0 when k is even. For general trees, $R_{Δ}$(T; s) ≤ 2s(Δ(T) − 1).To study sharpness of the upper bound, consider the $double-starS_{a,b}$, the tree whose two non-leaf vertices have degrees a and b. If a ≤ b, then $R_{Δ}(S_{a,b}$; 2) is 2b − 2 when a < b and b is even; it is 2b − 1 otherwise. If s is fixed and at least 3, then $R_{Δ}(S_{b,b}$;s) = f(s)(b − 1) − o(b), where f(s) = 2s − 3.5 − $O(s^{−1}$).We prove several results about edge-colourings of bounded-degree graphs that are related to degree Ramsey numbers of paths. Finally, for cycles we show that $R_{Δ}(C_{2k + 1}$; s) ≥ $2^{s}$ + 1, that $R_{Δ}(C_{2k}$; s) ≥ 2s, and that $R_{Δ}(C_{4}$;2) = 5. For the latter we prove the stronger statement that every graph with maximum degree at most 4 has a 2-edge-colouring such that the subgraph in each colour class has girth at least 5. |
| Related Links | http://www.math.uiuc.edu/~west/pubs/degram.pdf https://www.cambridge.org/core/services/aop-cambridge-core/content/view/931BEC5C7F977E0C5853852868EEF5AF/S0963548311000617a.pdf/div-class-title-degree-ramsey-numbers-of-graphs-div.pdf |
| Ending Page | 253 |
| Page Count | 25 |
| Starting Page | 229 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548311000617 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 1-2 |
| Volume Number | 21 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2012-03-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Edge Colouring Colour Class Degree Ramsey Numbers |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
