pith. sign in

arxiv: 2605.16542 · v1 · pith:4EKK2LLPnew · submitted 2026-05-15 · 🧮 math.CO

On Small Folkman Graphs Arrowing K₂ or K₃

Zohair Raza Hassan , Stanis{\l}aw Radziszowski , Steven Van Overberghe This is my paper

Pith reviewed 2026-05-20 16:14 UTC · model grok-4.3

classification 🧮 math.CO
keywords folkman numbersramsey arrowingedge coloringsw5-free graphssemi-polycirculant graphscombinatorial searchgraph theory
0
0 comments X

The pith

A W5-free graph exists that arrows (3,3) in every edge 2-coloring, proving F_e(3,3;W5) is finite.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper computes new upper bounds on small Folkman numbers F_v(a,b;H) and F_e(a,b;H) for a,b in {2,3}, k up to 4, and H drawn from complete graphs, near-complete graphs, C4, and W5. It does so by generating candidate graphs via several search techniques and verifying that each candidate avoids the chosen H while forcing a monochromatic K2 or K3 in every valid coloring. The central new result is an explicit construction establishing that F_e(3,3;W5) exists, so only one five-vertex graph remains open for the edge-arrowing case. Theoretical lemmas are supplied to guide future work on the final open vertex-arrowing instance.

Core claim

We prove the existence of F_e(3,3;W5) by exhibiting W5-free graphs that satisfy the edge-arrowing condition (3,3)^e. The same methods yield improved bounds on a collection of related Folkman numbers for forbidden subgraphs on four to six vertices, with most of the new examples arising from the semi-polycirculant graph generator.

What carries the argument

The semi-polycirculant graph generator, which enumerates candidate graphs that are then filtered for H-freeness and checked for the monochromatic-clique arrowing property in all colorings.

Load-bearing premise

The graphs output by the semi-polycirculant generator and the listed extension and filter routines are correctly verified to be free of the target forbidden subgraph and to arrow the required monochromatic cliques.

What would settle it

An independent computational or hand verification that one of the reported witness graphs on a stated number of vertices is W5-free yet contains a monochromatic triangle in every 2-edge-coloring of its edges.

Figures

Figures reproduced from arXiv: 2605.16542 by Stanis{\l}aw Radziszowski, Steven Van Overberghe, Zohair Raza Hassan.

Figure 1
Figure 1. Figure 1: Unique extremal (3, 3; J5) v -graph 4.2 Filters (⋆) The results marked with ⋆ in Tables 1 and 2 are computable using nauty’s geng with (pre-)filters: we wrote programs to check whether a given graph has H as a subgraph. Since geng generates graphs by adding one vertex at a time, it is possible to stop the construction as soon as the graph contains H as a subgraph. Note that in each of our cases, we can ass… view at source ↗
Figure 2
Figure 2. Figure 2: The unique graph in Fv(3, 3, 3; J6; 15) discussed in Sections 4.3 and 4.4. The colors are for clarity only: in blue is the complement of the Petersen graph, in green is a K5, in red are the connections between the two subgraphs. • Our witness graph for Fv(3, 3, 3; J6) can be seen as a five-vertex extension of the complement of the Petersen graph: Let X := {1, 2, 3, 4, 5}, V1 := X 1  and V2 := X 2  . G = … view at source ↗
read the original abstract

For a graph $G$ and integers $a_i \geq 1$, we say that $G \xrightarrow[]{} (a_1, \ldots, a_k)^v$ if in any $k$-coloring of $G$'s vertices there exists a monochromatic $a_i$-clique for some color $i \in \{1,\ldots,k\}$. $G \xrightarrow[]{} (a_1, \ldots, a_k)^e$ is defined similarly, but for edge colorings. The Folkman number $F_v(a_1, \ldots, a_k; H)$ is the smallest number of vertices for which an $H$-free graph arrowing $(a_1, \ldots, a_k)^v$ exists. $F_e(a_1, \ldots, a_k; H)$ is defined similarly for edge-arrowing. In this work, we present new bounds for Folkman numbers where $a_i \in \{2,3\}$ and $k \leq 4$, while avoiding $K_n$, $J_n$, for $n \in \{4,5,6\}$, where $K_n$ is the complete graph on $n$ vertices and $J_n$ is $K_n$ missing an edge. We also present results for $C_4$-free and $W_5$-free graphs, where $C_4$ is the cycle on four vertices and $W_5$ is the wheel graph on five vertices. Notably, we prove the existence of $F_e(3,3;W_5)$, leaving only one graph, $\overline{P_2 \cup P_3}$, on five vertices for which the existence problem of $F_e(3,3;H)$ remains open. We provide some theoretical results that should aid in uncovering the existence of $F_v(3,3; \overline{P_2 \cup P_3})$. Our new bounds are the result of a variety of methods involving filters, extension, semi-polycirculant graphs, locally linear graphs, and the modification of special graphs. Most of our bounds are from the semi-polycirculant graph generator, showcasing its efficacy for finding witness Folkman graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript defines Folkman numbers F_v(a1,...,ak;H) and F_e(a1,...,ak;H) for vertex- and edge-arrowing of small cliques while avoiding a forbidden subgraph H. It reports new upper bounds on these numbers for a_i in {2,3}, k≤4 and H ranging over K_n, J_n (n=4,5,6), C4, and W5. The central result is a constructive proof of existence for F_e(3,3;W5) obtained via a semi-polycirculant graph generator together with filters, extensions, and locally linear graphs; this leaves only one 5-vertex graph (overline{P2 ∪ P3}) for which the existence question remains open. Most bounds are claimed to arise from the semi-polycirculant construction.

Significance. If the computational witnesses are correctly verified, the work narrows the landscape of small Folkman numbers and supplies concrete, usable upper bounds. The semi-polycirculant generator is presented as an effective tool for producing H-free arrowing graphs; documenting its output would constitute a reusable contribution to the area.

major comments (2)
  1. [section describing the semi-polycirculant witness for F_e(3,3;W5)] The existence claim for F_e(3,3;W5) rests on a single computationally generated witness whose W5-freeness and arrowing property (every 2-edge-coloring contains a monochromatic K3) must be verified by exhaustive or symmetry-reduced search. The manuscript does not supply the adjacency list of this graph, the size of the search space explored, or the output of any SAT encoding or enumeration routine used to confirm the arrowing condition.
  2. [computational methods and results sections] For the new upper bounds obtained from the semi-polycirculant generator and the listed filters/extensions, the paper must state the precise verification procedure (e.g., number of colorings checked, symmetry group order, or solver certificate) that establishes both H-freeness and the arrowing property; without this, the bounds cannot be independently confirmed.
minor comments (2)
  1. [preliminaries] The definition of F_e(a1,...,ak;H) in the abstract is clear, but the manuscript should explicitly restate the precise meaning of 'H-free' (induced or not) when describing the generators.
  2. [introduction] Notation for the overline{P2 ∪ P3} graph is used without a figure or adjacency description; a small diagram would aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed and constructive report. We address each major comment below and have revised the manuscript to enhance the reproducibility of our computational results.

read point-by-point responses

  1. Referee: [section describing the semi-polycirculant witness for F_e(3,3;W5)] The existence claim for F_e(3,3;W5) rests on a single computationally generated witness whose W5-freeness and arrowing property (every 2-edge-coloring contains a monochromatic K3) must be verified by exhaustive or symmetry-reduced search. The manuscript does not supply the adjacency list of this graph, the size of the search space explored, or the output of any SAT encoding or enumeration routine used to confirm the arrowing condition.

    Authors: We agree that the manuscript should provide sufficient information to allow independent verification of the witness graph for F_e(3,3;W5). In the revised version we will include the adjacency list of the semi-polycirculant graph, the order of its automorphism group used for symmetry reduction, and a precise description of the verification procedure (including the number of colorings examined after reduction and the method used to confirm both W5-freeness and the monochromatic-K3 arrowing property). revision: yes

  2. Referee: [computational methods and results sections] For the new upper bounds obtained from the semi-polycirculant generator and the listed filters/extensions, the paper must state the precise verification procedure (e.g., number of colorings checked, symmetry group order, or solver certificate) that establishes both H-freeness and the arrowing property; without this, the bounds cannot be independently confirmed.

    Authors: We concur that explicit verification details are necessary for all computationally derived bounds. The revised manuscript will expand the computational methods section to specify, for each new upper bound, the symmetry group order employed, the number of colorings checked under that reduction, and any additional certificates or enumeration routines used to establish both H-freeness and the required arrowing property. revision: yes

Circularity Check

0 steps flagged

No significant circularity; existence via independent computational construction

full rationale

The paper establishes F_e(3,3;W5) by generating candidate graphs with the semi-polycirculant generator, applying W5-freeness filters, and verifying the arrowing property via exhaustive or symmetry-reduced checks on the resulting adjacency structure. This verification operates on the concrete output graph and is not equivalent to any input parameter or definition by construction. No equations, self-citations, or ansatzes reduce the existence claim to a tautology or fitted quantity. The approach is a standard constructive search whose correctness rests on implementation fidelity rather than definitional circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions of graph colorings and arrowing plus the correctness of a computational generator; no new mathematical constants or entities are introduced.

axioms (1)
  • standard math Basic properties of finite graphs, vertex/edge colorings, and clique formation under monochromatic constraints
    Invoked in the definitions of arrowing and Folkman numbers throughout the abstract.

pith-pipeline@v0.9.0 · 5972 in / 1317 out tokens · 55769 ms · 2026-05-20T16:14:35.896721+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

  1. [1]

    Z. R. Hassan and Y. Jiang and D. E. Narv. Graphs Comb. , volume =

    work page

  2. [2]

    Lazebnik and J

    F. Lazebnik and J. Verstra. Electronic Journal of Combinatorics , volume =

    work page

  3. [3]

    and Nenov, N

    Bikov, A. and Nenov, N. , journal=. 2017 , volume=

    work page 2017

  4. [4]

    and Radziszowski, S

    Coles, J. and Radziszowski, S. , journal=. 2006 , pages=

    work page 2006

  5. [5]

    Khadzhiivanov, N. D. and Nenov, N. , journal=. 1983 , myind=

    work page 1983

  6. [6]

    Piwakowski and S

    K. Piwakowski and S. Radziszowski and S. Urbański , title =. Journal of Graph Theory , volume =. 1999 , myind=

    work page 1999

  7. [7]

    Bikov and N

    A. Bikov and N. Nenov , title =. Australasian Journal of Combinatorics , volume =. 2020 , myind=

    work page 2020

  8. [8]

    Lange and S

    A. Lange and S. Radziszowski and X. Xu , title =. Journal of Combinatorial Mathematics and Combinatorial Computing , volume =. 2014 , pages =

    work page 2014

  9. [9]

    Graham, R. L. , journal=

    work page

  10. [10]

    and Verstra\"

    Lazebnik, F. and Verstra\". Electronic Journal of Combinatorics , VOLUME =. 2003 , ISSN =. doi:10.37236/1718 , URL =

    work page doi:10.37236/1718 2003

  11. [11]

    Chartrand and C.C

    G. Chartrand and C.C. Rousseau and M.J. Stewart and A.D. Polimeni and J. Sheehan , title =. Proceedings of the Fourth International Conference on the Theory and Applications of Graphs , YEAR =

    work page

  12. [12]

    B. D. McKay , title=. Journal of Algorithms , volume=. 1998 , doi=

    work page 1998

  13. [13]

    B. D. McKay and A. Piperno , title =. Journal of Symbolic Computation , Volume =. 2014 , Pages =

    work page 2014

  14. [14]

    and Van Maldeghem, H

    Pasini, A. and Van Maldeghem, H. , year =. Note di Matematica , doi =

    work page

  15. [15]

    and Van Overberghe, S

    Goedgebeur, J. and Van Overberghe, S. , title =. Discrete Applied Mathematics , volume =

    work page

  16. [16]

    Radziszowski , journal =

    S. Radziszowski , journal =. 2026 , url =

    work page 2026

  17. [17]

    Goedgebeur , title =

    J. Goedgebeur , title =. Journal of Graph Theory , volume =

    work page

  18. [18]

    , title =

    Folkman, J. , title =. SIAM Journal of Applied Mathematics , volume =. 1970 , pages =

    work page 1970

  19. [19]

    , title =

    Nenov, N. , title =. C.R. Acad. Bulgare Sci. , volume =. 1984 , pages =

    work page 1984

  20. [20]

    , title =

    Nenov, N. , title =. Annuaire Univ. Sofia Fac. Math. Inform. , volume =. 2000 , pages =

    work page 2000

  21. [21]

    , journal=

    Nenov, N. , journal=

    work page

  22. [22]

    , title =

    Nenov, N. , title =. Discrete Mathematics , volume =. 2003 , pages =

    work page 2003

  23. [23]

    , title =

    Nenov, N. , title =. Serdica Mathematical Journal , volume =. 2009 , pages =

    work page 2009

  24. [24]

    , title =

    Nenov, N. , title =. Annuaire Univ. Sofia Fac. Math. Inform. , volume =

    work page

  25. [25]

    2001 , pages =

    Discrete Mathematics , volume =. 2001 , pages =

    work page 2001

  26. [26]

    and Griffiths, S

    Fiz Pontiveros, G. and Griffiths, S. and Morris, R. , title =. 2020 , pages =

    work page 2020

  27. [27]

    and Luo, H

    Xu, X. and Luo, H. and Shao, Z. , title =. Electronic Journal of Combinatorics , volume =. 2010 , note =

    work page 2010

  28. [28]

    1996 , publisher=

    Periodica Mathematica Hungarica , volume=. 1996 , publisher=

    work page 1996

  29. [29]

    2001 , publisher=

    Discrete Mathematics , volume=. 2001 , publisher=

    work page 2001

  30. [30]

    Biere and T

    A. Biere and T. Faller and K. Fazekas and M. Fleury and N. Froleyks and F. Pollitt , title =. Proc. of

    work page

  31. [31]

    International Conference on Theory and Applications of Satisfiability Testing , pages=

    E. International Conference on Theory and Applications of Satisfiability Testing , pages=. 2003 , organization=

    work page 2003

  32. [32]

    Kolev, N. R. , journal=. 2008 , publisher=

    work page 2008

  33. [33]

    and Liang, M

    Deng, F. and Liang, M. and Shao, Z. and Xu, X. , journal=

    work page

  34. [34]

    W. J. Wesley , title =. Discrete Mathematics , volume =

    work page

  35. [35]

    Electronic Journal of Combinatorics , volume =

    Lidick. Electronic Journal of Combinatorics , volume =

    work page

  36. [36]

    , year =

    Van Overberghe, S. , year =

    work page

  37. [37]

    Mathematica Slovaca , volume=

    Fron. Mathematica Slovaca , volume=. 1989 , publisher=

    work page 1989

  38. [38]

    and Nomura, K

    Hiraki, A. and Nomura, K. and Suzuki, H. , title =. Journal of Algebraic Combinatorics , VOLUME =. 2000 , NUMBER =

    work page 2000

  39. [39]

    D. F. Holt and G. F. Royle , title =. J. Symb. Comput. , volume =

    work page

  40. [40]

    Brouwer, A. E. and Van Maldeghem, H. , volume=. 2022 , publisher=

    work page 2022

  41. [41]

    Electronic Journal of Combinatorics , author=

    Some New Ramsey Colorings , volume=. Electronic Journal of Combinatorics , author=. 1998 , month=. doi:10.37236/1367 , number=

    work page doi:10.37236/1367 1998