The Pancake Graph of Order 10 Is 4-Colorable
Authors: 
Renzo Roel Perez Tan, Aldrich Ellis Catapang Asuncion, Brian Godwin Sy Lim, Mate Soos, Kazushi IkedaAuthors Info & Claims
Pages 1 - 6
Abstract
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.
References
[1]
Sheldon Akers and Balakrishnan Krishnamurthy. 1989. A group-theoretic model for symmetric interconnection networks. IEEE Trans. Comput. 38, 4 (1989), 555–566.
[2]
Aldrich Asuncion, Renzo Tan, Christian Chan Shio, and Kazushi Ikeda. 2022. Recursive Linear Bounds for the Vertex Chromatic Number of the Pancake Graph. International Journal of Applied Mathematics 52, 1 (2022), 117–130.
[3]
Pascal Berthome, Afonso Ferreira, and Stephane Perennes. 1996. Optimal information dissemination in star and pancake networks. IEEE Transactions on Parallel and Distributed Systems 7, 12 (1996), 1292–1300.
[4]
Armin Biere. 2017. CaDiCaL, Lingeling, Plingeling, Treengeling, YalSAT Entering the SAT Competition 2017. In Proceedings of SAT Competition 2017 – Solver and Benchmark Descriptions(Department of Computer Science Series of Publications B, Vol. B-2017-1). University of Helsinki, 14–15.
[5]
John Bondy and Uppaluri Murty. 2008. Graph Theory. Springer.
[6]
Gary Chartrand and Ping Zhang. 2009. Chromatic graph theory. CRC Press.
[7]
Phillip Compeau. 1975. Girth of pancake graphs. Discrete Applied Mathematics 159 (1975), 1641–1645.
[8]
Stephen Cook. 1971. The Complexity of Theorem-Proving Procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing. ACM, 151–158.
[9]
Leen Droogendijk and Elena Konstantinova. In press. An improved bound on the chromatic number of the Pancake graphs. Discussiones Mathematicae Graph Theory (In press).
[10]
Harry Dweighter. 1975. Problem E2569. Amer. Math. Monthly 82 (1975), 1010.
[11]
Niklas Een and Niklas Sorensson. 2003. An Extensible SAT-solver. In Theory and Applications of Satisfiability Testing(Lecture Notes in Computer Science, Vol. 2919). Springer, 502–518.
[12]
Karmella Haynes, Marian Broderick, Adam Brown, Trevor Butner, James Dickson, Lance Harden, Lane Heard, Eric Jessen, Kelly Malloy, Brad Ogden, Sabriya Rosemond, Samantha Simpson, Erin Zwack, Malcolm Campbell, Todd Eckdahl, Laurie Heyer, and Jeffrey Poet. 2008. Engineering bacteria to solve the Burnt Pancake Problem. Journal of Biological Engineering 2, 8 (2008).
[13]
Arkady Kanevsky and Chao Feng. 1995. On the embedding of cycles in pancake graphs. Parallel Comput. 21, 6 (1995), 923–936.
[14]
Elena Konstantinova. 2017. Chromatic Properties of the Pancake Graphs. Discussiones Mathematicae Graph Theory 37, 3 (2017), 777–787.
[15]
Matthew Moskewicz, Conor Madigan, Ying Zhao, Lintao Zhang, and Sharad Malik. 2001. Chaff: Engineering an Efficient SAT Solver. In Proceedings of the 38th Design Automation Conference. ACM, 530–535.
[16]
Quan Nguyen and Said Bettayeb. 2011. On the Genus of Pancake Network. The International Arab Journal of Information Technology 8, 3 (2011), 289–292.
[17]
Bart Selman, Henry Kautz, and Bram Cohen. 1993. Local search strategies for satisfiability testing. In Cliques, Coloring, and Satisfiability(DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 26). DIMACS/AMS, 521–531.
Index Terms
- The Pancake Graph of Order 10 Is 4-Colorable
Recommendations
Acyclically 4-colorable triangulations
An acyclic k-coloring of a graph is a proper vertex k-coloring such that every bichromatic subgraph, induced by this coloring, contains no cycles. A graph is acyclically k-colorable if it has an acyclic k-coloring. In this paper, we prove that every ...
A Brooks-type bound for squares of K4 -minor-free graphs
Refining a bound by Lih, Wang and Zhu, we prove that if the square G^2 of a K"4-minor-free graph G with maximum degree @D>=6 does not contain a complete subgraph on @?32@D@?+1 vertices, then G^2 is @?32@D@?-colorable.
Ohba's conjecture for graphs with independence number five
Ohba has conjectured that if G is a k-chromatic graph with at most 2k+1 vertices, then the list chromatic number or choosability ch(G) of G is equal to its chromatic number @g(G), which is k. It is known that this holds if G has independence number at ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
160 pages
ISBN:9798400700187
DOI:10.1145/3613347
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 December 2023
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
Conference
ICoMS 2023
ICoMS 2023: 2023 6th International Conference on Mathematics and Statistics
July 14 - 16, 2023
Leipzig, Germany
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 28Total Downloads
- Downloads (Last 12 months)27
- Downloads (Last 6 weeks)2
Reflects downloads up to 03 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format