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 re...