Ramsey and Gallai-Ramsey Numbers for Two Classes of Unicyclic Graphs
- PDF / 364,676 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 40 Downloads / 208 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Ramsey and Gallai-Ramsey Numbers for Two Classes of Unicyclic Graphs Zhao Wang1 • Yaping Mao2,3 • Colton Magnant3,4
•
Jinyu Zou5
Received: 13 October 2019 / Revised: 20 September 2020 / Accepted: 23 October 2020 Springer Japan KK, part of Springer Nature 2020
Abstract Given a graph G and a positive integer k, define the Gallai-Ramsey number to be the minimum number of vertices n such that any k-edge coloring of Kn contains either a rainbow (all different colored) triangle or a monochromatic copy of G. In this paper, we consider two classes of unicyclic graphs, the star with an extra edge and the path with a triangle at one end. We provide the 2-color Ramsey numbers for these two classes of graphs and use these to obtain general upper and lower bounds on the Gallai-Ramsey numbers. Keywords Ramsey number Gallai-Ramsey number Unicyclic graph
Supported by the National Science Foundation of China (Nos. 12061059, 11601254, 11551001, 11161037, 61763041, 11661068, and 11461054) and the Qinghai Key Laboratory of Internet of Things Project (2017-ZJ-Y21). & Colton Magnant [email protected] Zhao Wang [email protected] Yaping Mao [email protected] Jinyu Zou [email protected] 1
College of Science, China Jiliang University, Hangzhou 310018, China
2
School of Mathematics and Statistis, Qinghai Normal University, Xining, Qinghai 810008, China
3
Academy of Plateau Science and Sustainability, Xining, Qinghai 810008, China
4
Advanced Analytics Group, United Parcel Service, Atlanta, GA, USA
5
Department of Basic Course, Qinghai University, Xining 810016, China
123
Graphs and Combinatorics
1 Introduction In this work, we consider only edge-colorings of graphs. A coloring of a graph is called rainbow if no two edges have the same color. Colorings of complete graphs that contain no rainbow triangle have very interesting and somewhat surprising structure. In 1967, Gallai [6] first examined this structure under the guise of transitive orientations. The result was reproven in [8] in the terminology of graphs and can also be traced to [1]. For the following statement, a trivial partition is a partition into only one part. Theorem 1 ([1, 6, 8]) In any coloring of a complete graph containing no rainbow triangle, there exists a nontrivial partition of the vertices (that is, with at least two parts) such that there are at most two colors on the edges between the parts and only one color on the edges between each pair of parts. For ease of notation, we refer to a colored complete graph with no rainbow triangle as a Gallai-coloring and the partition provided by Theorem 1 as a Gallaipartition. The induced subgraph of a Gallai colored complete graph constructed by selecting a single vertex from each part of a Gallai partition is called the reduced graph of that partition. By Theorem 1, the reduced graph is a 2-colored complete graph. Given two graphs G and H, let RðG; HÞ denote the 2-color Ramsey number for finding a monochromatic G or H, that is,
Data Loading...
