The Pancake Graph of Order 10 Is 4-Colorable
Document Type
Conference Proceeding
Publication Date
7-14-2023
Abstract
The pancake graph has served as a model for real-world networks due to its unique recursive and symmetric properties. Defined as the Cayley graph on the symmetric group of order n generated by prefix reversals, the n-pancake graph exhibits a rapid increase in the number of vertices and edges with respect to order n. While there are considerable graph-theoretic results on the graph, findings on chromatic properties for larger n are limited. In this paper, the 10-pancake graph is established to be 4-colorable through an efficient Boolean-satisfiability-based stochastic local search framework for vertex coloring. Building on the aforementioned, a new linear bound for the chromatic number of the pancake graph is put forward. In addition, the range of possible bounds that may be obtained from the same technique is determined.
Recommended Citation
Renzo Roel Perez Tan, Aldrich Ellis Catapang Asuncion, Brian Godwin Sy Lim, Mate Soos, and Kazushi Ikeda. 2023. The Pancake Graph of Order 10 Is 4-Colorable. In Proceedings of the 2023 6th International Conference on Mathematics and Statistics (ICoMS '23). Association for Computing Machinery, New York, NY, USA, 1–6. https://doi.org/10.1145/3613347.3613348
