On the packing chromatic number of Moore graphs. (English) Zbl 1454.05038
Summary: The packing chromatic number \( \chi_\rho ( G )\) of a graph \(G\) is the smallest integer \(k\) for which there exists a vertex coloring \(\Gamma : V ( G ) \to \{ 1 , 2 , \ldots , k \}\) such that any two vertices of color \(i\) are at distance at least \(i + 1\). For \(g \in \{ 6 , 8 , 12 \}\), \(( q + 1 , g )\)-Moore graphs are \(( q + 1 )\)-regular graphs with girth \(g\) which are the incidence graphs of a symmetric generalized \(g / 2\)-gons of order \(q\). In this paper we study the packing chromatic number of a \(( q + 1 , g )\)-Moore graph \(G\). For \(g = 6\) we present the exact value of \(\chi_\rho ( G )\). For \(g = 8\), we determine \(\chi_\rho ( G )\) in terms of the intersection of certain structures in generalized quadrangles. For \(g = 12\), we present lower and upper bounds for this invariant when \(q \geq 9\) is an odd prime power.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C12 | Distance in graphs |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 51E20 | Combinatorial structures in finite projective spaces |
| 51E12 | Generalized quadrangles and generalized polygons in finite geometry |
Software:
GAPReferences:
| [1] | Abreu, M.; Araujo, G.; Balbuena D. Labbate, C., A construction of small (q - 1)-regular graphs of girth 8, Electron. J. Combin., 22, 2, #P2.10 (2015) · Zbl 1310.05152 |
| [2] | Araujo-Pardo, G.; Balbuena, C.; Valenzuela, J. C., Constructions of bi-regular cages, Discete Math., 309, 6, 1409-1416 (2009) · Zbl 1229.05129 |
| [3] | Bagchi, B.; Sastry, N. S.N., Intersection pattern of the classical ovoids in symplectic 3-space of even order, J. Algebra, 126, 147-160 (1989) · Zbl 0685.51006 |
| [4] | Bailey, R.; Jackson, A.; Weir, C., Incidence graph of \(G H ( 3 , 3 ) (2019)\), Retrieved from http://www.distanceregular.org/graphs/incidence-gh3.3.html (May 20) |
| [5] | Balogh, J.; Kostochka, A.; Liu, Xujun, Packing chromatic number of cubic graphs, Discrete Math., 341, 2, 474-483 (2018) · Zbl 1376.05047 |
| [6] | Bannai, E.; Ito, T., On finite moore graphs j, Fac. Sci. Tokyo Sect. 1A, 20, 191-208 (1973) · Zbl 0275.05121 |
| [7] | Barlote, A., Una estensione del teorema di sergre-kustaanheimo, Boll. Un. Man. Ital., 10, 3, 498-506 (1955) · Zbl 0066.38901 |
| [8] | Bondy, J. A.; Murty, U. S.R., Graph Theory, GTM 244 (2008), Springer: Springer Berlin · Zbl 1134.05001 |
| [9] | Brešar, B.; Klavžar, S.; Rall, D. F., On the packing chromatic number of cartesian products, hexagonal lattice, and trees, Discrete Appl. Math., 155, 2303-2311 (2007) · Zbl 1126.05045 |
| [10] | Brešar, B.; Klavžar, S.; Rall, D. F., Packing chromatic number of base-3 sierpinski graphs, Graphs Combin, 1313-1327 (2016) · Zbl 1342.05111 |
| [11] | Cedillo, C.; MacKinney-Romero, R.; Pizaña, M. A.; Robles, I. A.; Villarroel-Flores, R., YAGS - Yet Another Graph System, Version 0.0.4; (2018), (http://xamanek.izt.uam.mx/yags/) |
| [12] | Damerell, R. M., On moore graphs, Proc. Cambridge Philos. Soc., 74, 227-236 (1973) · Zbl 0262.05132 |
| [13] | Ekstein, J.; Holub, P.; Lidický, B., Packing chromatic number of distance graphs, Discrete Appl. Math., 160, 518-524 (2012) · Zbl 1239.05050 |
| [14] | Exoo, G.; Jajcay, R., Dynamic cage survey, Electron. J. Combin., #DS16 (2013) · Zbl 1169.05336 |
| [15] | Finbow, A. S.; Rall, D. F., On the packing chromatic number of some lattices, Discrete Appl. Math., 158, 1224-1228 (2010) · Zbl 1221.05137 |
| [16] | Gastineau, N.; Holub, P.; Togni, O., On the packing chromatic number of subcubic outerplanar graphs, Discrete Appl. Math., 255, 209-221 (2019) · Zbl 1405.05060 |
| [17] | Goddard, W.; Hedetniemi, S. M.; Hedetniemi, S. T.; Harris, J. M.; Rall, D. F., Broadcast chromatic numbers of graphs, Ars Combin., 86, 33-49 (2008) · Zbl 1224.05172 |
| [18] | M. Kim, B. Lidický, T. Masr̆ík F. Pfender, Notes on complexity of packing coloring, Inform. Process. Lett. · Zbl 1478.68247 |
| [19] | Martin, B.; Raimondi, F.; Chen, T.; Martin, J., The packing chromatic number of the infinite square lattice is between 13 and 15, Discrete Appl. Math., 225, 136-142 (2017) · Zbl 1361.05051 |
| [20] | Miller, M.; S̆.irán̆, J., Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin., #DS14 (2013) · Zbl 1079.05043 |
| [21] | Payne, S. E.; Thas, J. A., Finite Generalized Quadrangles, vol. 9 (2009), European Mathematical Society · Zbl 1247.05047 |
| [22] | GAP - Groups, algorithms, and programming, version 4.10.1 (2019), (https://www.gap-system.org) |
| [23] | Torres, P.; Valencia-Pabon, M., The packing chromatic number of hypercubes, Discrete Appl. Math., 190-191, 127-140 (2015) · Zbl 1316.05050 |
| [24] | Van Maldeghem, H., Generalized Polygons (2012), Springer Science & Business Media · Zbl 0659.51010 |
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.
