A Ramsey bound for Seidel switches of claw-free graphs

1. The family and the result

Call a graph Ramsey-good if it contains neither a clique nor an independent set of order five. The ordinary Ramsey problem remains open between the bounds $43\leq R(5,5)\leq46$ [1]. This note excludes a complete structural family at the conjectured threshold.

Seidel switching across a partition $V=A\mathbin{\dot\cup}B$ reverses all adjacencies between $A$ and $B$ and preserves adjacencies within each part. A graph is claw-free if it has no induced $K_{1,3}$.

Theorem 1. Every graph on $43$ vertices that is switching-equivalent to a claw-free graph contains a clique or an independent set of order five. More generally, a Ramsey-good induced subgraph of a Seidel switch of any claw-free graph has at most $42$ vertices.

The class in Theorem 1 permits arbitrary claw-free parents and arbitrary switches, including those that destroy regularity or other symmetry. No assertion is made that an arbitrary Ramsey-good graph belongs to this class. Thus the theorem does not improve the ordinary Ramsey bounds.

The proof uses one restriction shared by the two parts of a switching cut. If a Ramsey-good graph switches to a claw-free graph, a cross edge has at most five common neighbors, and a cross nonedge has at most six. Counting the same common neighbors by their centers gives an upper bound on the combined internal and cross degrees. The Caro--Wei independence bound makes this upper bound incompatible with the minimum degree of a Ramsey-good graph of order $43$.

2. Established switching and coloring results

The family considered here is the upper claw-free switching class: some switch must be claw-free. This differs from requiring every switch to be claw-free. Antony, Cao, Pal and Sandeep [2] distinguish these classes and show that upper switching classes of hereditary graph classes are hereditary. Recognition of the upper claw-free class is already polynomial-time, by Jelínková and Kratochvíl [3]. The earlier paper of Jelínková, Suchý, Hliněný and Kratochvíl [4] explicitly credits that recognition result and displays the switching orbit $\{I_4,K_{1,3},C_4\}$. We use this elementary local orbit; we do not propose a new recognition algorithm. Our attribution of the recognition result is supported by [2,4]; its original algorithm is not a proof dependency here.

Restricted Ramsey numbers for hereditary graph classes are an established topic. For example, Alecu, Atminas, Lozin and Zamaraev [5, Section 4.1] determine the Ramsey numbers of graphs that are simultaneously claw-free and co-claw-free. Those hypotheses concern the graph itself and do not describe arbitrary switches of arbitrary claw-free parents. The contribution here is the finite bound in Theorem 1, obtained by coupling the two parts of the same switching cut.

For comparison, McDiarmid's fractional local coloring bound, stated as Theorem 3 of Chudnovsky, King, Plumettaz and Seymour [6], gives $\chi_f(H)\leq\max_v(d_H(v)+1+\omega_H(v))/2$. For a Ramsey-good quasi-line graph, each neighborhood is covered by two cliques of order at most three. Thus $\Delta(H)\leq6$, $\chi_f(H)\leq11/2$, and $|H|\leq\alpha(H)\chi_f(H)\leq22$. Applying this separately to the two unchanged parts gives order at most $44$ for switched quasi-line graphs. For general claw-free parts the analogous degree bound is eight and this argument gives at most $26$ vertices per part, hence only $52$ overall. Theorem 1 both covers the larger parent class and reaches order $42$ by using cross-part information.

3. A common-neighbor bound across the switching cut

Write $N_G(v)$ for the open neighborhood of $v$. The next lemma only requires exclusion of $K_5$, not exclusion of independent five-sets.

Lemma 2. Let $G$ be $K_5$-free, and suppose that switching across $V(G)=A\mathbin{\dot\cup}B$ gives a claw-free graph. For $u\in A$ and $v\in B$,

$$ |N_G(u)\cap N_G(v)|\leq \begin{cases} 5,&uv\in E(G),\\ 6,&uv\notin E(G). \end{cases} $$

Proof. Put $C=N_G(u)\cap N_G(v)$.

First suppose $uv$ is an edge. The set $C$ induces a triangle-free graph, since a triangle together with $u,v$ would give a $K_5$. It also contains no independent triple $T$. Indeed, both $G[T\cup \{u\}]$ and $G[T\cup\{v\}]$ would be claws. Switching a claw leaves a claw exactly when the switching set meets its four vertices evenly. The two intersections here have opposite parity, since $u,v$ lie on opposite sides of the cut. At least one claw would remain after switching. Thus $G[C]$ has neither a triangle nor an independent triple, and $|C|\leq5$ by $R(3,3)=6$.

Now suppose $uv$ is a nonedge. If two vertices $p,q\in C$ on the same side of the cut were nonadjacent, $G[\{u,v,p,q\}]$ would be a $C_4$ meeting the switching set oddly. An odd switch of $C_4$ is a claw. Therefore both $C\cap A$ and $C\cap B$ induce cliques. Each clique has order at most three: four of its vertices together with $u$ would give a $K_5$. Hence $|C|\leq6$. $\square$

For completeness, the local switching rules have a direct description. Each of $I_4$, a claw, and $C_4$ is complete bipartite on its four vertices, allowing an empty part. Switching changes the bipartition by symmetric difference with the switching set. The result is a claw exactly when its bipartition has odd part sizes. This proves both parity rules used in Lemma 2 without appealing to a recognition algorithm.

Let $s=|A|$, $t=|B|$, and let $E$ count the edges of $G$ crossing the cut. For each vertex $v$, denote its degree within its part by $a_v$ and its degree across the cut by $c_v$. Counting length-two paths with endpoints on opposite sides, first by their centers and then by their endpoints, gives

$$ \sum_v a_vc_v =\sum_{u\in A,\,v\in B}|N_G(u)\cap N_G(v)| \leq5E+6(st-E)=6st-E. $$

Since $\sum_v c_v=2E$, we obtain the shared capacity bound

$$ \boxed{\displaystyle\sum_v\left(a_v+\frac12\right)c_v\leq6st.} \tag{1} $$

4. The order-43 contradiction

Suppose $G$ is a Ramsey-good graph of order $43$ that switches across $A,B$ to a claw-free graph. Each of $G[A]$ and $G[B]$ is unchanged by switching and is therefore claw-free. A neighborhood within either part has no independent triple, by claw-freeness, and no clique of order four, by $K_5$-freeness. The classical value $R(3,4)=9$ gives

$$ 0\leq a_v\leq8. \tag{2} $$

The nonneighbors of any vertex of $G$ induce a graph with no clique of order five and no independent set of order four. Since $R(4,5)=25$, there are at most $24$ such nonneighbors. Consequently

$$ a_v+c_v\geq18,\qquad c_v\geq18-a_v. \tag{3} $$

The small Ramsey values used here are standard and recorded in the survey [7].

We also use the classical Caro--Wei inequality $\alpha(J)\geq\sum_{v\in V(J)}1/(d_J(v)+1)$. Its short proof is included to make the independence step explicit: order the vertices of $J$ uniformly at random and select each vertex that precedes all its neighbors. The selected vertices form an independent set, and their expected number is the displayed sum. Applied to each part, it gives

$$ \sum_v\frac1{a_v+1} \leq\alpha(G[A])+\alpha(G[B])\leq8. \tag{4} $$

For every integer $a\in\{0,\ldots,8\}$,

$$ \left(a+\frac12\right)(18-a) \geq\frac{225}{2}-\frac{495}{2(a+1)}. \tag{5} $$

Indeed, multiplying the difference by $2(a+1)$ gives $(4-a)(8-a)(9-2a)$. For $a\leq4$ all factors are nonnegative. For $5\leq a\leq8$ the first and third are nonpositive and the second is nonnegative. This proves (5).

Equations (2)--(5) now imply

$$ \begin{aligned} \sum_v\left(a_v+\frac12\right)c_v &\geq\sum_v\left(a_v+\frac12\right)(18-a_v)\\ &\geq\frac{225\cdot43}{2} -\frac{495}{2}\sum_v\frac1{a_v+1}\\ &\geq\frac{225\cdot43-495\cdot8}{2} =\frac{5715}{2}. \end{aligned} $$

But $s+t=43$ implies $st\leq21\cdot22$, so (1) gives the upper bound $2772$. The contradiction gap is

$$ \frac{5715}{2}-2772=\frac{171}{2}>0. $$

This proves Theorem 1 at order $43$. Switching commutes with induced deletion and claw-freeness is hereditary. Any larger Ramsey-good retained graph would therefore have a forbidden order-$43$ induced subgraph. $\square$

5. Consequences, limits and verification

By complementation the same bound holds for the switching closure of co-claw-free graphs. The number $42$ is an upper bound for both families; attainability is not established. The proof does not determine the exact restricted Ramsey number or classify smaller extremizers. It supplies no premise placing all Ramsey-good graphs in either family.

The mathematical evidence is the complete proof above. It uses no catalogue completeness, SAT exclusion, symmetry assumption or graph enumeration at order $43$. The supplement contains a standard-library Python diagnostic for the local implications, the path-count identity, and the nine exact rational inequalities. Run python src/check_clawfree_switching_bound.py from its extracted root. It checks all labeled good five-vertex graphs and switching cuts up to complementation, 120 seeded arbitrary graph/cut instances, and the displayed scalar gap. These checks are controls for the derivation; they are not substitutes for its universal proof or evidence of attainability at order $42$.

References

[1] V. Angeltveit and B. D. McKay. $R(5,5)\leq46$. 2024. https://arxiv.org/abs/2409.15709

[2] D. Antony, Y. Cao, S. Pal and R. B. Sandeep. Switching Classes: Characterization and Computation. 2024, version 2. https://arxiv.org/abs/2403.04263v2

[3] E. Jelínková and J. Kratochvíl. On Switching to H-Free Graphs. Journal of Graph Theory 75 (2014), 387--405. https://doi.org/10.1002/jgt.21745

[4] E. Jelínková, O. Suchý, P. Hliněný and J. Kratochvíl. Parameterized Problems Related to Seidel's Switching. Discrete Mathematics & Theoretical Computer Science 13(2) (2011), 19--42. https://doi.org/10.46298/dmtcs.542

[5] B. Alecu, A. Atminas, V. Lozin and V. Zamaraev. Graph classes with linear Ramsey numbers. Discrete Mathematics 344 (2021), 112307. https://arxiv.org/abs/1910.12109

[6] M. Chudnovsky, A. D. King, M. Plumettaz and P. Seymour. A local strengthening of Reed's $\omega,\Delta,\chi$ conjecture for quasi-line graphs. 2011, version 2. https://arxiv.org/abs/1109.2112v2

[7] S. P. Radziszowski. Small Ramsey Numbers. Electronic Journal of Combinatorics, Dynamic Survey DS1. https://doi.org/10.37236/21