The Pancake Graph of Order 10 Is 4-Colorable

• Main Authors: Tan, Renzo Roel Perez, Asuncion, Aldrich Ellis Catapang, Lim, Brian Godwin Sy, Soos, Mate, Ikeda, Kazushi
• Format: text
• Published: Archīum Ateneo 2023
• Subjects: Boolean satisfiability; chromatic number; linear bounds; pancake graph; vertex coloring; Mathematics; Physical Sciences and Mathematics; Statistics and Probability
• Online Access: https://archium.ateneo.edu/mathematics-faculty-pubs/237; https://doi.org/10.1145/3613347.3613348
• Institution: Ateneo De Manila University

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.