×

zbMATH — the first resource for mathematics

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:
GAP
PDF BibTeX XML Cite
Full Text: DOI
References:
[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)
[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)
[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 06889952
[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)
[21] Payne, S. E.; Thas, J. A., Finite Generalized Quadrangles, vol. 9 (2009), European Mathematical Society
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.