Chromatic properties of the Pancake graphs. (English) Zbl 1366.05043
Summary: Chromatic properties of the Pancake graphs \(P_n\), \(n\geq2\), that are Cayley graphs on the symmetric group \(\mathrm{Sym}_n\) generated by prefix-reversals are investigated in the paper. It is proved that for any \(n\geq3\) the total chromatic number of \(P_n\) is \(n\), and it is shown that the chromatic index of \(P_n\) is \(n-1\). We present upper bounds on the chromatic number of the Pancake graphs \(P_n\), which improve R. L. Brooks’ bound for \(n\geq7\) [Proc. Camb. Philos. Soc. 37, 194–197 (1941; Zbl 0027.26403)] and P. A. Catlin’s bound for \(n\leq28\) [Discrete Math. 21, 81–83 (1978; Zbl 0374.05023)]. Algorithms of a total \(n\)-coloring and a proper \((n-1)\)-coloring are given.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
References:
| [1] | O.V. Borodin and A.V. Kostochka, On an upper bound of a graph’s chromatic number depending on the graph’s degree and destiny, J. Combin. Theory. Ser. B. 23 (1977) 247-250. doi:10.1016/0095-8956(77)90037-5; · Zbl 0336.05104 |
| [2] | R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37 (1941) 194-197. doi:10.1017/S030500410002168X; · Zbl 0027.26403 |
| [3] | P.A. Catlin, A bound on the chromatic number of a graph, Discrete Math. 22 (1978) 81-84. doi:10.1016/0012-365X(78)90049-3; |
| [4] | P.A. Catlin, Another bound on the chromatic number of a graph, Discrete Math. 24 (1978) 1-6. doi:10.1016/0012-365X(78)90167-X; · Zbl 0384.05043 |
| [5] | I.J. Dejter and O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Math. 129 (2003) 319-328. doi:10.1016/S0166-218X(02)00573-5; · Zbl 1035.05060 |
| [6] | H. Dweighter, E 2569 in: Elementary problems and solutions, Amer. Math. Monthly 82 (1975) 1010.; |
| [7] | A. Johansson, Asymptotic choice number for triangle free graphs, DIMACS Technical Report (1996) 91-95.; |
| [8] | A. Kanevsky and C. Feng, On the embedding of cycles in Pancake graphs, Parallel Comput. 21 (1995) 923-936. doi:10.1016/0167-8191(94)00096-S; · Zbl 0875.68708 |
| [9] | E. Konstantinova, On some structural properties of Star and Pancake graphs, Lecture Notes in Comput. Sci. 7777 (2013) 472-487. doi:10.1007/978-3-642-36899-8_23; · Zbl 1377.05159 |
| [10] | E. Konstantinova and A. Medvedev, Independent even cycles in the Pancake graph and greedy Prefix-reversal Gray codes, Graphs Combin. 32 (2016) 1965-1978. doi:10.1007/s00373-016-1679-x; · Zbl 1349.05198 |
| [11] | J.J. Sheu, J.J.M. Tan and K.T. Chu, Cycle embedding in Pancake interconnection networks, in: Proc. 23rd Workshop on Combinatorial Mathematics and Computation Theory (Taiwan, 2006) 85-92.; |
| [12] | K. Qiu, Optimal broadcasting algorithms for multiple messages on the Star and Pancake graphs using minimum dominating sets, Congr. Numer. 181 (2006) 33-39.; · Zbl 1114.05097 |
| [13] | V.G. Vizing, Some unsolved problems in graph theory, Uspekhi Mat. Nauk 23 (1968) 117-134. doi:10.1070/rm1968v023n06abeh001252; · Zbl 0177.52301 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
