Solving Graph Coloring Problems with Abstraction and Symmetry
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$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Computing the Ramsey Number R(4,3,3) using Abstraction and Symmetry breaking
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 almost 50 years. This paper presents a methodology based …
JCOL: A Java package for solving the graph coloring problem
The graph coloring problem aims at assigning colors to the nodes of a graph such that no two connected nodes have the same color. The graph coloring problem is NP-complete and one of the harder problems to solve. Here we…
Population-based Gradient Descent Weight Learning for Graph Coloring Problems
Graph coloring involves assigning colors to the vertices of a graph such that two vertices linked by an edge receive different colors. Graph coloring problems are general models that are very useful to formulate many rel…
Learning Discrete Abstractions for Visual Rearrangement Tasks Using Vision-Guided Graph Coloring
Learning abstractions directly from data is a core challenge in robotics. Humans naturally operate at an abstract level, reasoning over high-level subgoals while delegating execution to low-level motor skills -- an abili…
Evaluating the Systematic Reasoning Abilities of Large Language Models through Graph Coloring
Contemporary large language models are powerful problem-solving tools, but they exhibit weaknesses in their reasoning abilities which ongoing research seeks to mitigate. We investigate graph coloring as a means of evalua…
Benchmarking