Sub-Ramsey Numbers for Matchings

Fangfang Wu; Shenggui Zhang; Binlong Li

doi:10.1007/s00373-020-02216-2

Sub-Ramsey Numbers for Matchings

Fangfang Wu, Shenggui Zhang, Binlong Li

School of Mathematics and Statistics

Northwestern Polytechnical University Xian

Research output: Contribution to journal › Article › peer-review

Abstract

Given a graph G and a positive integer k, the sub-Ramsey number sr(G, k) is defined to be the minimum number m such that every K_m whose edges are colored using every color at most k times contains a subgraph isomorphic to G all of whose edges have distinct colors. In this paper, we will concentrate on sr(nK₂, k) with nK₂ denoting a matching of size n. We first give upper and lower bounds for sr(nK₂, k) and exact values of sr(nK₂, k) for some n and k. Afterwards, we show that sr(nK₂, k) = 2 n when n is sufficiently large and k<n8 by applying the Local Lemma.

Original language	English
Pages (from-to)	1675-1685
Number of pages	11
Journal	Graphs and Combinatorics
Volume	36
Issue number	6
DOIs	https://doi.org/10.1007/s00373-020-02216-2
State	Published - 1 Nov 2020

Keywords

Local lemma
Rainbow matchings
Sub-Ramsey number

Access to Document

10.1007/s00373-020-02216-2

Cite this

@article{4803b466fb6546c0b64395c1215035c4,

title = "Sub-Ramsey Numbers for Matchings",

abstract = "Given a graph G and a positive integer k, the sub-Ramsey number sr(G, k) is defined to be the minimum number m such that every Km whose edges are colored using every color at most k times contains a subgraph isomorphic to G all of whose edges have distinct colors. In this paper, we will concentrate on sr(nK2, k) with nK2 denoting a matching of size n. We first give upper and lower bounds for sr(nK2, k) and exact values of sr(nK2, k) for some n and k. Afterwards, we show that sr(nK2, k) = 2 n when n is sufficiently large and k",

keywords = "Local lemma, Rainbow matchings, Sub-Ramsey number",

author = "Fangfang Wu and Shenggui Zhang and Binlong Li",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Japan KK, part of Springer Nature.",

year = "2020",

month = nov,

day = "1",

doi = "10.1007/s00373-020-02216-2",

language = "英语",

volume = "36",

pages = "1675--1685",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "6",

}

TY - JOUR

T1 - Sub-Ramsey Numbers for Matchings

AU - Wu, Fangfang

AU - Zhang, Shenggui

AU - Li, Binlong

PY - 2020/11/1

Y1 - 2020/11/1

N2 - Given a graph G and a positive integer k, the sub-Ramsey number sr(G, k) is defined to be the minimum number m such that every Km whose edges are colored using every color at most k times contains a subgraph isomorphic to G all of whose edges have distinct colors. In this paper, we will concentrate on sr(nK2, k) with nK2 denoting a matching of size n. We first give upper and lower bounds for sr(nK2, k) and exact values of sr(nK2, k) for some n and k. Afterwards, we show that sr(nK2, k) = 2 n when n is sufficiently large and k

AB - Given a graph G and a positive integer k, the sub-Ramsey number sr(G, k) is defined to be the minimum number m such that every Km whose edges are colored using every color at most k times contains a subgraph isomorphic to G all of whose edges have distinct colors. In this paper, we will concentrate on sr(nK2, k) with nK2 denoting a matching of size n. We first give upper and lower bounds for sr(nK2, k) and exact values of sr(nK2, k) for some n and k. Afterwards, we show that sr(nK2, k) = 2 n when n is sufficiently large and k

KW - Local lemma

KW - Rainbow matchings

KW - Sub-Ramsey number

UR - https://www.scopus.com/pages/publications/85088513149

U2 - 10.1007/s00373-020-02216-2

DO - 10.1007/s00373-020-02216-2

M3 - 文章

AN - SCOPUS:85088513149

SN - 0911-0119

VL - 36

SP - 1675

EP - 1685

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 6

ER -

Sub-Ramsey Numbers for Matchings

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this