Solving Graph Coloring Problems with Abstraction and Symmetry
This work addresses a fundamental open problem in combinatorics and graph theory, with potential implications for Ramsey theory, but it is incremental as it provides evidence rather than a full proof.
The paper tackles the long-standing problem of determining the Ramsey number R(4,3,3), providing evidence that it equals 30 by showing there are exactly 78,892 (3,3,3;13) Ramsey colorings and that any (4,3,3;30) coloring must be (13,8,8) regular.
This paper introduces a general methodology, based on abstraction and symmetry, that applies to solve hard graph edge-coloring problems and demonstrates its use to provide further evidence that the Ramsey number $R(4,3,3)=30$. The number $R(4,3,3)$ is often presented as the unknown Ramsey number with the best chances of being found "soon". Yet, its precise value has remained unknown for more than 50 years. We illustrate our approach by showing that: (1) there are precisely 78{,}892 $(3,3,3;13)$ Ramsey colorings; and (2) if there exists a $(4,3,3;30)$ Ramsey coloring then it is (13,8,8) regular. Specifically each node has 13 edges in the first color, 8 in the second, and 8 in the third. We conjecture that these two results will help provide a proof that no $(4,3,3;30)$ Ramsey coloring exists implying that $R(4,3,3)=30$.