The Library
Edges not in any monochromatic copy of a fixed graph
Tools
Tools
Tools
Liu, Hong, Pikhurko, Oleg and Sharifzadeh, Maryam (2019) Edges not in any monochromatic copy of a fixed graph. Journal of Combinatorial Theory, Series B, 135 . pp. 16-43. doi:10.1016/j.jctb.2018.07.007 ISSN 0095-8956.
|
PDF
WRAP-edges-not-monochromatic-copy-fixed-graph-Liu-2018.pdf - Accepted Version - Requires a PDF viewer. Download (722Kb) | Preview |
Official URL: https://doi.org/10.1016/j.jctb.2018.07.007
Abstract
For a sequence ( H i ) k i =1 of graphs, let nim( n ; H 1 ,...,H k ) denote the maximum number of edges not contained in any monochromatic copy of H i in colour i , for any colour i , over all k -edge- colourings of K n .
When each H i is connected and non-bipartite, we introduce a variant of Ramsey number that determines the limit of nim( n ; H 1 ,...,H k ) / ( n 2 ) as n → ∞ and prove the corresponding stability result. Furthermore, if each H i is what we call homomorphism-critical (in particular if each H i is a clique), then we determine nim( n ; H 1 ,...,H k ) exactly for all sufficiently large n . The special case nim( n ; K 3 ,K 3 ,K 3 ) of our result answers a question of Ma.
For bipartite graphs, we mainly concentrate on the two-colour symmetric case (i.e., when k = 2 and H 1 = H 2 ). It is trivial to see that nim( n ; H,H ) is at least ex( n,H ), the maximum size of an H -free graph on n vertices. Keevash and Sudakov showed that equality holds if H is the 4-cycle and n is large; recently Ma extended their result to an infinite family of bipartite graphs. We provide a larger family of bipartite graphs for which nim( n ; H,H ) = ex( n,H ). For a general bipartite graph H , we show that nim( n ; H,H ) is always within a constant additive error from ex( n,H ), i.e., nim( n ; H,H ) = ex( n,H ) + O H (1).
| Item Type: | Journal Article | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||||||||
| Library of Congress Subject Headings (LCSH): | Graph coloring, Graph theory | |||||||||||||||
| Journal or Publication Title: | Journal of Combinatorial Theory, Series B | |||||||||||||||
| Publisher: | Academic Press | |||||||||||||||
| ISSN: | 0095-8956 | |||||||||||||||
| Official Date: | March 2019 | |||||||||||||||
| Dates: |
|
|||||||||||||||
| Volume: | 135 | |||||||||||||||
| Page Range: | pp. 16-43 | |||||||||||||||
| DOI: | 10.1016/j.jctb.2018.07.007 | |||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||
| Publication Status: | Published | |||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
| Date of first compliant deposit: | 26 July 2018 | |||||||||||||||
| Date of first compliant Open Access: | 24 July 2019 | |||||||||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
