Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMinimal Ramsey graphs with many vertices of small degree
111
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given any graph $H$, a graph $G$ is said to be $q$-Ramsey for $H$ if every coloring of the edges of $G$ with $q$ colors yields a monochromatic subgraph isomorphic to $H$. Further, such a graph $G$ is said to be minimal $q$-Ramsey for $H$ if additionally no proper subgraph $G$ of $G$ is $q$-Ramsey for $H$. In 1976, Burr, ErdH{o}s, and Lovasz initiated the study of the parameter $s_q(H)$, defined as the smallest minimum degree among all minimal $q$-Ramsey graphs for $H$. In this paper, we consider the problem of determining how many vertices of degree $s_q(H)$ a minimal $q$-Ramsey graph for $H$ can contain. Specifically, we seek to identify graphs for which a minimal $q$-Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property $s_q$-abundant. Among other results, we prove that every cycle is $s_q$-abundant for any integer $qgeq 2$. We also discuss the cases when $H$ is a clique or a clique with a pendant edge, extending previous results of Burr et al. and Fox et al. To prove our results and construct suitable minimal Ramsey graphs, we develop certain new gadget graphs, called pattern gadgets, which generalize and extend earlier constructions that have proven useful in the study of minimal Ramsey graphs. These new gadgets might be of independent interest.
rate research
Read More
We prove that $s_r(K_k) = O(k^5 r^{5/2})$, where $s_r(K_k)$ is the Ramsey parameter introduced by Burr, ErdH{o}s and Lov{a}sz in 1976, which is defined as the smallest minimum degree of a graph $G$ such that any $r$-colouring of the edges of $G$ contains a monochromatic $K_k$, whereas no proper subgraph of $G$ has this property. The construction used in our proof relies on a group theoretic model of generalised quadrangles introduced by Kantor in 1980.
Halin showed that every edge minimal, k-vertex connected graph has a vertex of degree k. In this note, we prove the analogue to Halins theorem for edge-minimal, k-edge-connected graphs. We show there are two vertices of degree k in every edge-minimal, k-edge-connected graph.
A graph $G$ is said to be $q$-Ramsey for a $q$-tuple of graphs $(H_1,ldots,H_q)$, denoted by $Gto_q(H_1,ldots,H_q)$, if every $q$-edge-coloring of $G$ contains a monochromatic copy of $H_i$ in color $i,$ for some $iin[q]$. Let $s_q(H_1,ldots,H_q)$ denote the smallest minimum degree of $G$ over all graphs $G$ that are minimal $q$-Ramsey for $(H_1,ldots,H_q)$ (with respect to subgraph inclusion). The study of this parameter was initiated in 1976 by Burr, ErdH{o}s and Lovasz, who determined its value precisely for a pair of cliques. Over the past two decades the parameter $s_q$ has been studied by several groups of authors, the main focus being on the symmetric case, where $H_icong H$ for all $iin [q]$. The asymmetric case, in contrast, has received much less attention. In this paper, we make progress in this direction, studying asymmetric tuples consisting of cliques, cycles and trees. We determine $s_2(H_1,H_2)$ when $(H_1,H_2)$ is a pair of one clique and one tree, a pair of one clique and one cycle, and when it is a pair of two different cycles. We also generalize our results to multiple colors and obtain bounds on $s_q(C_ell,ldots,C_ell,K_t,ldots,K_t)$ in terms of the size of the cliques $t$, the number of cycles, and the number of cliques. Our bounds are tight up to logarithmic factors when two of the three parameters are fixed.
We study graphs with the property that every edge-colouring admits a monochromatic cycle (the length of which may depend freely on the colouring) and describe those graphs that are minimal with this property. We show that every member in this class reduces recursively to one of the base graphs $K_5-e$ or $K_4vee K_4$ (two copies of $K_4$ identified at an edge), which implies that an arbitrary $n$-vertex graph with $e(G)geq 2n-1$ must contain one of those as a minor. We also describe three explicit constructions governing the reverse process. As an application we are able to establish Ramsey infiniteness for each of the three possible chromatic subclasses $chi=2, 3, 4$, the unboundedness of maximum degree within the class as well as Ramsey separability of the family of cycles of length $leq l$ from any of its proper subfamilies.
Given two graphs $G$ and $H$, the $k$-colored Gallai-Ramsey number $gr_k(G : H)$ is defined to be the minimum integer $n$ such that every $k$-coloring of the complete graph on $n$ vertices contains either a rainbow copy of $G$ or a monochromatic copy of $H$. In this paper, we consider $gr_k(K_3 : H)$ where $H$ is a connected graph with five vertices and at most six edges. There are in total thirteen graphs in this graph class, and the Gallai-Ramsey numbers for some of them have been studied step by step in several papers. We determine all the Gallai-Ramsey numbers for the remaining graphs, and we also obtain some related results for a class of unicyclic graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
