The Pancake Graph of Order 10 Is 4-Colorable
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...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | text |
| Published: |
Archīum Ateneo
2023
|
| Subjects: | |
| Online Access: | https://archium.ateneo.edu/mathematics-faculty-pubs/237 https://doi.org/10.1145/3613347.3613348 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Ateneo De Manila University |
| Summary: | 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. |
|---|