The Pancake Graph of Order 10 Is 4-Colorable

Document Type

Conference Proceeding

Publication Date



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.