On the Size of (K-t,P-k)-Co-Critical Graphs

Chen, Gang1; Miao, Zhengke2,3; Song, Zi-Xia4; Zhang, Jingmei5

2022-10-01

10.1007/s00373-022-02531-w

GRAPHS AND COMBINATORICS   影响因子和分区

0911-0119

1435-5914

["Given graphs G, H-1, ..., H-k, we write G -> (H-1, ..., H-k) if every k-coloring tau : E(G) -> [k] contains a monochromatic copy of H-i in color i for some color i is an element of [k], where [k] = {1, ..., k} . A non-complete graph G is (H-1, ..., H-k)-co-critical if G negated right arrow(H-1, ..., H-k), but G + e -> (H-1, ..., H-k) for every edge e in (G) over bar. Motivated by a conjecture of Hanson and Toft from 1987, there are now a variety of papers studying the minimum number of possible edges over all (H-1, ..., H-k)-co-critical graphs. It seems non-trivial to construct extremal (H-1, ..., H-k)-co-critical graphs in general. In this paper, we focus on the study of the minimum number of edges over all (Kt, Pk)co-critical graphs, where Pk denotes the path on k >= 3 vertices. Using the minimum path cover of a graph, we prove that for t is an element of {3, 4, 5} and all k >= 4, there exists a constant C(t, k) such that, for all n >= (2t - 3)(k - 1) + inverted right perpendiculark/2inverted left perpendicular (inverted right perpendiculark/2inverted left perpendicular - 1) + 1, there exists a (K-t, P-k)-co-critical graph G on n vertices satisfying","e(G) <= (4t - 9/2 + 1/2 inverted right perpendiculark/2right perpendicular)n + C(t,k).","We then establish the sharp bound for the size of (K-3, P-4)-co-critical graphs on n >= 14 vertices by showing that all such graphs have at least [(5n - 3)/2] edges."]

Ramsey-minimal Co-critical graphs K-t-saturated

SCI

英语

非南科大

NSF[DMS-1854903]

Mathematics

Mathematics

WOS:000838085400001

SPRINGER JAPAN KK

MATHEMATICS

Web of Science

1.Ningxia Univ, Sch Math & Stat, Yinchuan 750021, Ningxia, Peoples R China
2.Jiangsu Normal Univ, Res Inst Math Sci, Xuzhou 221116, Jiangsu, Peoples R China
3.Jiangsu Normal Univ, Dept Math & Stat, Xuzhou 221116, Jiangsu, Peoples R China
4.Univ Cent Florida, Dept Math, Orlando, FL 32816 USA
5.Southern Univ Sci & Technol, High Sch, Shenzhen 518133, Guangdong, Peoples R China

Chen, Gang,Miao, Zhengke,Song, Zi-Xia,et al. On the Size of (K-t,P-k)-Co-Critical Graphs[J]. GRAPHS AND COMBINATORICS,2022,38(5).

Chen, Gang,Miao, Zhengke,Song, Zi-Xia,&Zhang, Jingmei.(2022).On the Size of (K-t,P-k)-Co-Critical Graphs.GRAPHS AND COMBINATORICS,38(5).

Chen, Gang,et al."On the Size of (K-t,P-k)-Co-Critical Graphs".GRAPHS AND COMBINATORICS 38.5(2022).