On Some Generalized
Vertex Folkman Numbers

All graphs considered in this paper are finite undirected simple graphs. The order of the largest independent set in graph $G$ will be denoted by $\alpha(G)$, and the chromatic number of $G$ by $\chi(G)$. Let $J_{k}$ be the complete graph $K_{k}$ missing one edge, i.e., $J_{k}=K_{k}-e$. Note that $J_{3}$ is the path on 3 vertices, and the diamond graph $J_{4}$ is formed by two triangles sharing an edge.

For a graph $G$ and integers $a_{1},\dots,a_{r}$, such that $a_{i}\geq 1$ for $1\leq i\leq r$, the expression $G\rightarrow(a_{1},\dots,a_{r})^{v}$ means that for any $r$-coloring of the vertices of $G$ there exists a monochromatic $a_{i}$-clique in $G$ for some color $i\in\{1,\cdots,r\}$. In this paper, we call this property vertex-arrowing, or simply arrowing. It should be noted that an analogous edge-arrowing property $G\rightarrow(a_{1},\dots,a_{r})^{e}$ is the basis of widely studied Ramsey edge-arrowing problems. In particular, the Ramsey number $R(a_{1},\dots,a_{r})$ is defined as the smallest integer $n$ such that $K_{n}\rightarrow(a_{1},\dots,a_{r})^{e}$. All our results address vertex-arrowing, but in some places we will refer to edge-arrowing for comparison, context, or when used as a tool. The vertex Folkman numbers $F_{v}$ are defined as

where $H$ is a graph and $G$ is called $H$-free if it does not contain $H$ as a subgraph (in contrast to a commonly used definition of $H$-free where it is required that $G$ does not contain $H$ as an induced subgraph). If $a_{i}=a$ for all $i$, then we use a more compact notation, $F_{v}(a^{r};H)=F_{v}(a_{1},\dots,a_{r};H)$. The set of all $H$-free graphs satisfying the arrowing $G\rightarrow(a_{1},\dots,a_{r})^{v}$ will be denoted by $\mathcal{F}_{v}(a_{1},\dots,a_{r};H)$ and we will call it the set of Folkman graphs for the corresponding parameters. Further, $\mathcal{F}_{v}(a_{1},\dots,a_{r};H;n)$ will denote a subset of the latter when restricted to graphs on $n$ vertices.

Let us set $m=1+\sum_{i=1}^{r}(a_{i}-1)$. We will often use the following lemma by Nenov [20] stating a simple necessary condition for vertex arrowing to hold.

Observe that if $a_{i}=2$ for all $i$, $1\leq i\leq r$, then the converse is also true. In the terms of Folkman numbers, this means that $F_{v}(2^{r};H)$ is equal to the smallest number of vertices in any $H$-free graph $G$ with $\chi(G)=r+1=m$. Note also that if $a_{i}=1$ for any color $i$, then essentially this color can be disregarded.

The vertex Folkman numbers have been extensively studied when the avoided graph is complete, i.e., when $H=K_{s}$ (see [10, 19, 16, 7, 33, 21, 22]). They are well defined when $s>\max\{a_{i}\ |\ 1\leq i\leq r\}$, since it is known that for such $s$ the minimum in the definition ranges over a nonempty set of graphs. The situation is easy for $s\geq m$. Moreover, much is known about vertex Folkman numbers and the corresponding Folkman graphs when $s$ is close to, but less than, $m$. However, even some of the basic questions become difficult for small $s$, such as $s=3$ or $s=4$. One of the famous problems which can be stated in these terms is the task of finding the smallest triangle-free graph with given chromatic number $r$, which is equal to $F_{v}(2^{r-1};K_{3})$. See the following subsection for references and more details about this problem in relation to our current work. A recent Ph.D. thesis by Bikov [1] presents a variety of Folkman problems, focusing on a computational approach together with the known values and bounds for Folkman numbers.

For graphs $F$ and $G$, the Ramsey number $R(F,G)$ is the smallest integer $n$ such that if the edges of $K_{n}$ are 2-colored, say red and blue, then necessarily this coloring includes a copy of red-colored $F$ or a copy of blue-colored $G$. If $F$ and $G$ are complete graphs, then we write $R(s,t)$ instead of $R(K_{s},K_{t})$. A regularly updated survey Small Ramsey Numbers [30] contains the known bounds and values for a variety of Ramsey numbers.

In this work we focus on the vertex Folkman numbers for graphs avoiding $H=J_{k}$, in particular for $k=4$ and $2\leq a_{i}\leq 3$. Note that this special case of $J_{4}$-free graphs admits some triangles, but not too many, since in $J_{4}$-free graphs each edge can belong to at most one triangle. We observe that avoiding $J_{4}$ falls in-between the two extensively studied classical cases of avoiding $K_{3}$ and $K_{4}$. Also for $H=J_{4}$, we see that $F_{v}(2^{r};J_{4})$ is the smallest number of vertices in any $J_{4}$-free graph with chromatic number $r+1$. These numbers are clearly well defined since any $K_{3}$-free graph is also $J_{4}$-free, and $F_{v}(2^{r};K_{3})$ is well defined for every $r\geq 1$. Furthermore, the classical results for multicolor Folkman numbers by Nešetřil and Rödl [25, 26] guarantee the existence of $F_{v}(3^{r};K_{s})$ for $s\geq 4$ and of $F_{v}(3,3;J_{4})$, while little less known results by Nešetřil and Rödl [24] and Rödl and Sauer [31] imply also the existence of $F_{v}(3^{r};J_{4})$ with $r>2$.

This subsection summarizes our contributions. They consist mainly of new lower and upper bounds for some concrete Folkman numbers, which were obtained with the help of computations (Theorems 3–7), but also new interesting graph constructions. Several special graphs were found during our computations, but we think that some of them (see Figures 1–4) are interesting just by themselves.

We start with Theorem 2, which is theoretical. This result is not new, as it is implied by more general old results by Nešetřil and Rödl [25, 24, 26], and more directly it follows from Theorem 1.2 in the work by Rödl and Sauer [31]. In the next section, we include our proof of Theorem 2 addressing directly the case of avoiding $J_{4}$.

The $J_{4}$-free graphs satisfying the required arrowing property in Theorem 2 quickly become very large as $r$ grows. The simplest, but already intriguing case, is that of $F_{v}(3,3;J_{4})$, for which we establish the upper bound of 135 in Theorem 7. Note that, by monotonicity, Theorem 2 implies the existence of Folkman numbers of the form $F_{v}(a_{1},\dots,a_{r};J_{4})$ with $a_{i}\leq 3$ for all $1\leq i\leq r$.

A $J_{4}$-free graph $G$ is called maximal $J_{4}$-free if the addition of any edge creates a $J_{4}$ in $G$. A graph $G$ for which $G\rightarrow(a_{1},\dots,a_{r})$ is called minimal if after the deletion of any edge this arrowing does not hold. If $G$ is maximal and minimal, it is referred to as bicritical. Using computational methods, we obtain the exact values and bounds for several small cases, as stated in Theorems 3–7 below.

For the context and comparison with the cases involving $K_{3}$ and $K_{4}$ instead of $J_{4}$, we collect the values and bounds from Theorems 3–5 in Table 1. Observe that since $K_{3}\subset J_{4}\subset K_{4}$, we must have $F_{v}(2^{r};K_{3})\geq F_{v}(2^{r};J_{4})\geq F_{v}(2^{r};K_{4})$, for each $r$.

The following sections contain our proof of Theorem 2, the description of computations leading to Theorems 3–7, and graph constructions. The closing section states some open problems and it contains a few remarks for parameters beyond those studied in this paper. The witness graphs for Theorems 3–7, as well as the code implementing algorithm A in Section 3.1 are available at https://www.cs.rochester.edu/~dnarvaez/folkmanj4/.

We found a few discrepancies between our results and those claimed in the paper [13]. We investigated all such differences, and we arrived to the conclusion that the computations reported in [13] were incomplete. The computational results reported in this paper were obtained by independent implementations which agreed on the final and intermediate claims. The main implementation described throughout this paper produced all reported results, except those involving SAT-solvers in Section 3.4. Two others implementations were used to corroborate various parts of these results and to manage the interface in Section 3.4.

In this section we describe the computations which were performed to obtain the proofs of Theorems 3–7 stated in Section 1.2. First, we give an overview of the algorithms that were used or developed for this work, including some details of their implementation. In the following subsections we summarize the results of our computations. We present graphs establishing the upper bounds in Theorems 3–6, and give counts for several intermediate graph families which were obtained. All graphs involved in the computations were $J_{4}$-free. The target sets of graphs had additional constraints consisting of the number of vertices, independence number, chromatic number, and the desired parameters of arrowing, $\{a_{1},\dots,a_{r}\}$, where $2\leq a_{i}\leq 3$ for $1\leq i\leq r$.

The basis of our software framework consisted of the package nauty developed by McKay [17], which includes a powerful graph generator geng, tools to remove graph isomorphs, and several other utilities for graph manipulation. In the following, we will list some of the graphs in their g6-format, a compact string representation of graphs in nauty. These graphs are also available at https://www.cs.rochester.edu/~dnarvaez/folkmanj4/.

The template of our main Extension Algorithm A is presented and commented on below. We also implemented filters for extracting graphs with specified chromatic number, graph which are maximal $J_{4}$-free, those which arrow $(2,3)^{v}$ and $(3,3)^{v}$, and other utilities. Observe that by Lemma 1 the test for arrowing $(2^{r})^{v}$ is the same as for chromatic number.

The graph families pointed to in Table 2 were obtained by using geng with filters for $J_{4}$-free graphs and for graphs with given chromatic number. For graph families on 13 or more vertices, we used mainly algorithm A together with other utilities, as described in the notes to Table 3.

Our custom filter for graphs with specified chromatic number range was tuned to process large number of graphs with small $\chi(G)$. For a given graph $G$, first we find all maximal independent sets, and then determine $\chi(G)$ as the minimum number of these independent sets which cover $V_{G}$. The custom filter for maximal $J_{4}$-free graphs has two modes: a full test detecting graphs for which addition of any edge forms a $J_{4}$, and a partial test for graphs being constructed within algorithm A which cannot be maximal $J_{4}$-free after A terminates. The latter permitted to significantly prune the output of A, which was then filtered through the full test.

Testing whether $G\rightarrow(2,3)^{v}$ was applied only to graphs with $\chi(G)\geq 4$, since by Lemma 1 this arrowing does not hold if $\chi(G)\leq 3$. This test was done by checking that for every maximal independent set $I\subset V_{G}$ the set of vertices $(V_{G}\setminus I)$ does not induce any triangle. The test for $G\rightarrow(2,2,3)^{v}$ was accomplished similarly by checking that the set of vertices $(V_{G}\setminus(I_{1}\cup I_{2}))$ does not induce any triangle, for every pair of maximal independent sets $I_{1}$ and $I_{2}$. The test for $G\rightarrow(3,3)^{v}$ was accomplished with a totally distinct approach involving SAT-solvers as described in Section 3.4. This was necessary since for arrowing $(3,3)^{v}$ we were processing a large number of graphs on 100 to 200 vertices, for which an effective handling of their chromatic number and enumeration of maximal triangle-free sets would be computationally very expensive.

Next, we give a high-level pseudocode of the Extension Algorithm A followed by comments explaining some of its components in more detail.

The new edges of $H$ are defined by $q$ cones $\{C_{1},\dots,C_{q}\}$, $C_{i}\subseteq V_{G}$, where the set of edges connecting $v_{i}$ to $V_{G}$ is $\{\{v_{i},u\}\ |\ u\in C_{i}\}$. First, we precompute the set of all feasible cones $\mathcal{C}_{G}$ such that for each $C\in\mathcal{C}_{G}$ the 1-vertex extension of $G$ using $C$ is $J_{4}$-free and $|C|\geq\delta$. We also precompute a binary predicate $\tau(C,D)$ on pairs of feasible cones which is false if $C\cap D=\emptyset$, $C\cap D=\{x\}$ and there is no vertex $y\in(C\setminus D)\cup(D\setminus C)$ connected to $x$, or $C\cap D$ induces an edge in $G$. Otherwise, $\tau(C,D)$ is set to true. One can easily see that if $\tau(C,D)$ is false and both cones $C$ and $D$ are used in the extension, then $H$ is not maximal $J_{4}$-free. This test significantly prunes the search space. Next, we assemble $q$-tuples of feasible cones such that each pair of cones used passes the $\tau$-test. Each such $q$-tuple defines one graph $H$. Finally, the isomorphic copies of graphs are removed, and the remaining graphs $H$ are tested for $\chi(H)$.

The cases for small $q\leq 2$ do not require the inner for-loop, since they essentially reduce to the computation of feasible cones ($q=1$) and $\tau$ ($q=2$), respectively. $\square$

Note that larger values of input $\delta$ in A produce fewer cones and thus allow for faster computation. Maximal $J_{4}$-free graphs $H$ with $\delta=1$ are easy to characterize theoretically (in particular they have $\chi=3$), and once they were confirmed by running A, in all further computations we set $\delta\geq 2$. For most of our computations we use $\delta=2$, but we also observe that when constructing graph families which are known to be $\chi$-vertex-critical, it is sufficient to set $\delta=\chi-1$.

The values of the Ramsey numbers of the form $R(J_{4},K_{q})$ are known for all $q\leq 6$ (cf. [30]). In particular, the values of importance to our computations are $R(J_{4},K_{4})=11$, $R(J_{4},K_{5})=16$ and $R(J_{4},K_{6})=21$. We use these values to determine the value of parameter $q$ for algorithm ${\bf A}$ by applying an observation that any $J_{4}$-free graph $H$ must have $\alpha(H)\geq q$, provided $|V_{H}|=|V_{G}|+q\geq R(J_{4},K_{q})$.

Sections 3.2 and 3.3 list several sets of parameters for A which were used: $\mathcal{G}$ is taken from the cases reported in Table 2, or equal to $\mathcal{F}_{v}(2,3;J_{4};14)$ or $\mathcal{F}_{v}(2^{4};J_{4};15)$, and the ranges of other parameters are $1\leq q\leq 7$, $4\leq\chi\leq 6$, and $2\leq\delta\leq\chi-1$.

The results of our computations for small cases are summarized in Tables 2 and 3. The special graphs, which are witnesses for the exact values in Theorems 3, 4 and 6, are presented in Figures 1–4.

Easy bounds on the order of the smallest 6-chromatic $J_{4}$-free graph, $F_{v}(2^{5};J_{4})$, are implied in prior work by others on avoiding $K_{3}$ and $K_{4}$ (see Table 1 in Section 1.2), namely:

We obtain much better bounds stated in Theorem 5:

These bounds were computed as follows. Take $S$ to be the Schläfli graph on 27 vertices [32]: $S$ is a strongly regular graph of degree 16. Its complement is $J_{4}$-free and it has $\chi(\overline{S})=6$. Removing from $\overline{S}$ any two adjacent vertices with all incident edges yields a 25-vertex witness to $F_{v}(2^{5};J_{4})\leq 25$ (the g6-format of this graph is XIPA@CQA_KEBIIHKBHGicBXB_w}auURYbDu_maULkdQTseOfpp?). Removing any further vertices reduces the chromatic number below 6. It is interesting to note that this witness graph is the unique 6-vertex-critical $(P_{6},J_{4},K_{4})$-induced-free¹¹1There is no induced subgraph isomorphic to a $J_{4}$, $K_{4}$, or $P_{6}$. graph on 25 vertices [11].

For the lower bound, since $R(J_{4},K_{6})=21$, any 21-vertex $J_{4}$-free graph must have an independent set of 6 vertices. Thus, any graph $G\in\mathcal{F}_{v}(2^{5};J_{4};21)$ can be obtained by adding a 6-independent set (with 6 cones) to one of the 5 graphs in $\mathcal{F}_{v}(2^{4};J_{4};15)$. This was verified with algorithm A and no suitable graph was found with $\chi\geq 6$. Thus $F_{v}(2^{5};J_{4})\geq 22$. This part proves Theorem 5.

The bounds we have for $F_{v}(2,2,3;J_{4})$ are rather weak, namely

The upper bound follows from Theorem 7 and by an easy observation that for any graph $G$, if $G\rightarrow(3,3)^{v}$, then $G\rightarrow(2,2,3)^{v}$. For the lower bound, suppose that $G\in\mathcal{F}_{v}(2,2,3;J_{4};k)$. Note that by Lemma 1, we must have $\chi(G)\geq 5$. For $k=19$, since $R(J_{4},K_{5})=16$, we have $\alpha(G)\geq 5$, and thus $G$ is a 5-vertex extension of at least one of the 212 graphs in $\mathcal{F}_{v}(2,3;J_{4};14)$. Using again algorithm A we have found no suitable graph $G$, and hence $k>19$. We attempted to use A and other ad-hoc methods to construct a witness $G$ for $k\geq 20$, but all such searches failed. The complement of the Schläfli graph $\overline{S}$ does not arrow $(2,2,3)^{v}$. We also tested 8933 $J_{4}$-free graphs $G$ on 20 vertices with $\chi(G)=\alpha(G)=5$ [29] and found that none of them arrows $(2,2,3)^{v}$. For comparison with the cases for $K_{4}$-free graphs, we note that it is not hard to check that $F_{v}(2,3;K_{4})=7$ with the unique witness graph $K_{7}-C_{7}$ (cf. Theorem 3 in [16]), and it is known that $F_{v}(2,2,3;K_{4})=14$ [5].

Finding any non-obvious bounds for $F_{v}(2,3,3;J_{4})$ or $F_{v}(3,3,3;J_{4})$ is an interesting challenge which we pose as a problem to work on.

The triangle-free process begins with an empty graph of order $n$, and iteratively adds edges chosen uniformly at random, subject to the constraint that no triangle is formed. The triangle-free process has been used to prove that

which currently is the best known lower bound for $R(3,t)$ obtained by Bohman and Keevash in 2013/2019 [3] and independently by Fiz Pontiveros, Griffiths and Morris in 2013/2020 [8].

Similarly to the triangle-free process, the $J_{4}$-free process begins with an empty graph of order $n$, and iteratively adds edges chosen uniformly at random, subject to the constraint that no $J_{4}$ is formed. The asymptotic properties of this process were analyzed in [27]. We implemented the $J_{4}$-free process in C++ and generated several graphs for which we then checked the arrowing property. The check was done by turning the arrowing property into a Boolean formula and then using Boolean satisfiability (SAT) solvers on the resulting formula. The formula is computed as follows: for every triple of vertices $(v_{1},v_{2},v_{3})$, if they form a triangle, we output the disjunctions

A satisfying assignment for this subformula will assign at least one of the vertices in $\{v_{1},v_{2},v_{3}\}$ to the value False and at least one of them to the value True. Taking False and True to be colors, it is clear that for a graph $G$ the formula

It is easy to see that $G\rightarrow(3,3)^{v}$ implies $K_{1}+G\rightarrow(3,3)^{e}$, where the graph $K_{1}+G$ is obtained from $G$ by adding one new vertex connected to all of $V_{G}$. By applying this implication we can also see that $F_{e}(3,3;K_{1}+H)\leq F_{v}(3,3;H)+1$. The latter inequality is tight for $H=K_{4}$, as it was shown that $F_{e}(3,3;K_{5})=15$ and $F_{v}(3,3;K_{4})=14$ (upper bounds in [18], lower bounds in [28]). Now, using similar steps for $H=J_{4}$, by Theorem 7 we obtain $F_{e}(3,3;J_{5})\leq 136$. We observe that by the monotonicity with respect to the avoided graph $H$ we have $F_{e}(3,3;K_{5})\leq F_{e}(3,3;J_{5})\leq F_{e}(3,3;K_{4})$.

The software development for this project, pilot runs and experiments spanned several months. Now, the final run of everything is doable in about a day in a standard lab with dozen of machines, each with 16 cores.