Recursive Linear Bounds for the Vertex Chromatic Number of the Pancake Graph

• Main Authors: Asuncion, Aldrich Ellis C, Tan, Renzo Roel P, Chan Shio, Christian, Ikeda, Kazushi
• Format: text
• Published: Archīum Ateneo 2022
• Subjects: chromatic number; linear bound; pancake graph; vertex coloring; Mathematics
• Online Access: https://archium.ateneo.edu/mathematics-faculty-pubs/183; https://archium.ateneo.edu/cgi/viewcontent.cgi?article=1189&context=mathematics-faculty-pubs
• Institution: Ateneo De Manila University

The pancake graph has been the subject of research. While studies on the various aspects of the graph are abundant, results on the chromatic properties may be further enhanced. Revolving around such context, the paper advances an alternative method to produce novel linear bounds for the vertex chromatic number of the pancake graph. The accompanying demonstration takes advantage of symmetries inherent to the graph, capturing the prefix reversal of subsequences through a homomorphism. Contained within the argument is the incorporation of known vertex chromatic numbers for certain orders of pancake graphs, rendering tighter bounds possible upon the release of new findings. In closing, a comparison with existing bounds is done to establish the relative advantage of the proposed technique.