اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRamsey equivalence of $K_n$ and $K_n+K_{n-1}$ for multiple colours
96
0
0.0
(
0
)
تأليف
Damian Reding
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In 2015 Bloom and Liebenau proved that $K_n$ and $K_n+K_{n-1}$ possess the same $2$-Ramsey graphs for all $ngeq 3$ (with a single exception for $n=3$). In the following we give a simple proof that $K_n$ and $K_n+K_{n-1}$ possess the same $r$-Ramsey graphs for all $n, rgeq 3$.
قيم البحث
اقرأ أيضاً
For an integer $qge 2$, a graph $G$ is called $q$-Ramsey for a graph $H$ if every $q$-colouring of the edges of $G$ contains a monochromatic copy of $H$. If $G$ is $q$-Ramsey for $H$, yet no proper subgraph of $G$ has this property then $G$ is called
$q$-Ramsey-minimal for $H$. Generalising a statement by Burr, Nev{s}etv{r}il and Rodl from 1977 we prove that, for $qge 3$, if $G$ is a graph that is not $q$-Ramsey for some graph $H$ then $G$ is contained as an induced subgraph in an infinite number of $q$-Ramsey-minimal graphs for $H$, as long as $H$ is $3$-connected or isomorphic to the triangle. For such $H$, the following are some consequences. (1) For $2le r< q$, every $r$-Ramsey-minimal graph for $H$ is contained as an induced subgraph in an infinite number of $q$-Ramsey-minimal graphs for $H$. (2) For every $qge 3$, there are $q$-Ramsey-minimal graphs for $H$ of arbitrarily large maximum degree, genus, and chromatic number. (3) The collection ${{cal M}_q(H) : H text{ is 3-connected or } K_3}$ forms an antichain with respect to the subset relation, where ${cal M}_q(H)$ denotes the set of all graphs that are $q$-Ramsey-minimal for $H$. We also address the question which pairs of graphs satisfy ${cal M}_q(H_1)={cal M}_q(H_2)$, in which case $H_1$ and $H_2$ are called $q$-equivalent. We show that two graphs $H_1$ and $H_2$ are $q$-equivalent for even $q$ if they are $2$-equivalent, and that in general $q$-equivalence for some $qge 3$ does not necessarily imply $2$-equivalence. Finally we indicate that for connected graphs this implication may hold: Results by Nev{s}etv{r}il and Rodl and by Fox, Grinshpun, Liebenau, Person and Szabo imply that the complete graph is not $2$-equivalent to any other connected graph. We prove that this is the case for an arbitrary number of colours.
The Harary--Hill conjecture, still open after more than 50 years, asserts that the crossing number of the complete graph $K_n$ is $ H(n) = frac 1 4 leftlfloorfrac{mathstrut n}{mathstrut 2}rightrfloor leftlfloorfrac{mathstrut n-1}{mathstrut 2}rightrfl
oor leftlfloorfrac{mathstrut n-2}{mathstrut 2}rightrfloor leftlfloorfrac{mathstrut n-3}{mathstrut 2}right rfloor$. Abrego et al. introduced the notion of shellability of a drawing $D$ of $K_n$. They proved that if $D$ is $s$-shellable for some $sgeqlfloorfrac{n}{2}rfloor$, then $D$ has at least $H(n)$ crossings. This is the first combinatorial condition on a drawing that guarantees at least $H(n)$ crossings. In this work, we generalize the concept of $s$-shellability to bishellability, where the former implies the latter in the sense that every $s$-shellable drawing is, for any $b leq s-2$, also $b$-bishellable. Our main result is that $(lfloor frac{n}{2} rfloor!-!2)$-bishellability of a drawing $D$ of $K_n$ also guarantees, with a simpler proof than for $s$-shellability, that $D$ has at least $H(n)$ crossings. We exhibit a drawing of $K_{11}$ that has $H(11)$ crossings, is 3-bishellable, and is not $s$-shellable for any $sgeq5$. This shows that we have properly extended the class of drawings for which the Harary-Hill Conjecture is proved. Moreover, we provide an infinite family of drawings of $K_n$ that are $(lfloor frac{n}{2} rfloor!-!2)$-bishellable, but not $s$-shellable for any $sgeqlfloorfrac{n}{2}rfloor$.
In studying properties of simple drawings of the complete graph in the sphere, two natural questions arose for us: can an edge have multiple segments on the boundary of the same face? and is each face the intersection of sides of 3-cycles? The second
is asserted to be obvious in two previously published articles, but when asked, authors of both papers were unable to provide a proof. We present a proof. The first is quite easily proved and the technique yields a third, even simpler, fact: no three edges at a vertex all have internal points incident with the same face.
Waiter-Client games are played on some hypergraph $(X,mathcal{F})$, where $mathcal{F}$ denotes the family of winning sets. For some bias $b$, during each round of such a game Waiter offers to Client $b+1$ elements of $X$, of which Client claims one f
or himself while the rest go to Waiter. Proceeding like this Waiter wins the game if she forces Client to claim all the elements of any winning set from $mathcal{F}$. In this paper we study fast strategies for several Waiter-Client games played on the edge set of the complete graph, i.e. $X=E(K_n)$, in which the winning sets are perfect matchings, Hamilton cycles, pancyclic graphs, fixed spanning trees or factors of a given graph.
K{a}rolyi, Pach, and T{o}th proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement generalizes to other classes of drawings, specifically, to simple draw
ings of the complete graph. These are drawings where edges are represented by Jordan arcs, any two of which intersect at most once. We present two partial results towards such a generalization. First, we show that the statement holds for cylindrical simple drawings. (In a cylindrical drawing, all vertices are placed on two concentric circles and no edge crosses either circle.) Second, we introduce a relaxation of the problem in which the graph is $k$-edge-colored, and the target structure must be hypochromatic, that is, avoid (at least) one color class. In this setting, we show that every $lceil (n+5)/6rceil$-edge-colored monotone simple drawing of $K_n$ contains a hypochromatic plane spanning tree. (In a monotone drawing, every edge is represented as an $x$-monotone curve.)
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
