×

Packing colorings of subcubic outerplanar graphs. (English) Zbl 1447.05074

Summary: Given a graph \(G\) and a nondecreasing sequence \(S=(s_1,\ldots ,s_k)\) of positive integers, the mapping \(c:V(G)\longrightarrow \{1,\ldots ,k\}\) is called an \(S\)-packing coloring of \(G\) if for any two distinct vertices \(x\) and \(y\) in \(c^{-1}(i)\), the distance between \(x\) and \(y\) is greater than \(s_i\). The smallest integer \(k\) such that there exists a \((1,2,\ldots ,k)\)-packing coloring of a graph \(G\) is called the packing chromatic number of \(G\), denoted \(\chi_{\rho }(G)\). The question of boundedness of the packing chromatic number in the class of subcubic (planar) graphs was investigated in several earlier papers; recently it was established that the invariant is unbounded in the class of all subcubic graphs. In this paper, we prove that the packing chromatic number of any 2-connected bipartite subcubic outerplanar graph is bounded by 7. Furthermore, we prove that every subcubic triangle-free outerplanar graph has a (1, 2, 2, 2)-packing coloring, and that there exists a subcubic outerplanar graph with a triangle that does not admit a (1, 2, 2, 2)-packing coloring. In addition, there exists a subcubic triangle-free outerplanar graph that does not admit a (1, 2, 2, 3)-packing coloring. A similar dichotomy is shown for bipartite outerplanar graphs: every such graph admits an \(S\)-packing coloring for \(S=(1,3,\ldots ,3)\), where 3 appears \(\Delta\) times \(( \Delta\) being the maximum degree of vertices), and this property does not hold if one of the integers 3 is replaced by 4 in the sequence \(S\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C12 Distance in graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Agnarsson, G.; Halldórsson, M., Vertex coloring the square of outerplanar graphs of low degree, Discuss. Math. Graph Theory, 30, 619-636 (2010) · Zbl 1217.05056 · doi:10.7151/dmgt.1518
[2] Argiroffo, G.; Nasini, G.; Torres, P., The packing coloring problem for lobsters and partner limited graphs, Discrete Appl. Math., 164, 373-382 (2014) · Zbl 1288.05078 · doi:10.1016/j.dam.2012.08.008
[3] Balogh, J.; Kostochka, A.; Liu, X., Packing chromatic number of subcubic graphs, Discrete Math., 341, 474-483 (2018) · Zbl 1376.05047 · doi:10.1016/j.disc.2017.09.014
[4] Balogh, J.; Kostochka, A.; Liu, X., Packing chromatic number of subdivisions of cubic graphs, Graphs Combin., 35, 2019, 513-537 (2019) · Zbl 1409.05080 · doi:10.1007/s00373-019-02016-3
[5] Barnaby, M.; 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 · doi:10.1016/j.dam.2017.03.013
[6] Brešar, B.; Ferme, J., An infinite family of subcubic graphs with unbounded packing chromatic number, Discrete Math., 341, 2337-2342 (2018) · Zbl 1388.05059 · doi:10.1016/j.disc.2018.05.004
[7] Brešar, B.; Klavžar, S.; Rall, DF, On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Appl. Math., 155, 2303-2311 (2007) · Zbl 1126.05045 · doi:10.1016/j.dam.2007.06.008
[8] Brešar, B.; Klavžar, S.; Rall, DF, Packing chromatic number of base-3 Sierpiński graphs, Graphs Combin., 32, 1313-1327 (2016) · Zbl 1342.05111 · doi:10.1007/s00373-015-1647-x
[9] Brešar, B.; Klavžar, S.; Rall, DF; Wash, K., Packing chromatic number under local changes in a graph, Discrete Math., 340, 1110-1115 (2017) · Zbl 1357.05037 · doi:10.1016/j.disc.2016.09.030
[10] Brešar, B.; Klavžar, S.; Rall, DF; Wash, K., Packing chromatic number, \((1,1,2,2)\)-colorings, and characterizing the Petersen graph, Aequ. Math., 91, 169-184 (2017) · Zbl 1355.05194 · doi:10.1007/s00010-016-0461-8
[11] Ekstein, J.; Holub, P.; Togni, O., The packing coloring of distance graphs \(D(k, t)\), Discrete Appl. Math., 167, 100-106 (2014) · Zbl 1284.05213 · doi:10.1016/j.dam.2013.10.036
[12] Fiala, J.; Golovach, PA, Complexity of the packing coloring problem for trees, Discrete Appl. Math., 158, 771-778 (2010) · Zbl 1219.05185 · doi:10.1016/j.dam.2008.09.001
[13] Fiala, J.; Klavžar, S.; Lidický, B., The packing chromatic number of infinite product graphs, Eur. J. Combin., 30, 1101-1113 (2009) · Zbl 1207.05165 · doi:10.1016/j.ejc.2008.09.014
[14] Finbow, A.; Rall, DF, On the packing chromatic number of some lattices, Discrete Appl. Math., 158, 1224-1228 (2010) · Zbl 1221.05137 · doi:10.1016/j.dam.2009.06.001
[15] Gastineau, N.; Togni, O., \(S\)-packing colorings of cubic graphs, Discrete Math., 339, 2461-2470 (2016) · Zbl 1339.05134 · doi:10.1016/j.disc.2016.04.017
[16] Gastineau, N.; Holub, P.; Togni, O., On packing chromatic number of subcubic outerplanar graphs, Discrete Appl. Math., 255, 209-221 (2019) · Zbl 1405.05060 · doi:10.1016/j.dam.2018.07.034
[17] Goddard, W.; Hedetniemi, SM; Hedetniemi, ST; Harris, JM; Rall, DF, Broadcast chromatic numbers of graphs, Ars Combin., 86, 33-49 (2008) · Zbl 1224.05172
[18] Jacobs, Y.; Jonck, E.; Joubert, EJ, A lower bound for the packing chromatic number of the Cartesian product of cycles, Cent. Eur. J. Math., 11, 1344-1357 (2013) · Zbl 1266.05121
[19] Korže, D.; Vesel, A., On the packing chromatic number of square and hexagonal lattice, Ars Math. Contemp., 7, 13-22 (2014) · Zbl 1302.05142 · doi:10.26493/1855-3974.255.88d
[20] Laïche, D.; Bouchemakh, I.; Sopena, E., On the packing coloring of undirected and oriented generalized theta graphs, Australas. J. Combin., 66, 310-329 (2016) · Zbl 1375.05094
[21] Lih, K-W; Wang, W-F, Coloring the square of an outerplanar graph, Taiwan. J. Math., 10, 1015-1023 (2006) · Zbl 1135.05022 · doi:10.11650/twjm/1500403890
[22] Shao, Z.; Vesel, A., Modeling the packing coloring problem of graphs, Appl. Math. Model., 39, 3588-3595 (2015) · Zbl 1443.05077 · doi:10.1016/j.apm.2014.11.060
[23] Sloper, C., An eccentric coloring of trees, Australas. J. Combin., 29, 309-321 (2004) · Zbl 1058.05026
[24] Soukal, R.; Holub, P., A note on packing chromatic number of the square lattice, Electron. J. Combin., 17, 447-468 (2010) · Zbl 1215.05050 · doi:10.37236/466
[25] Togni, O., On packing colorings of distance graphs, Discrete Appl. Math., 167, 280-289 (2014) · Zbl 1284.05109 · doi:10.1016/j.dam.2013.10.026
[26] Torres, P.; Valencia-Pabon, M., The packing chromatic number of hypercubes, Discrete Appl. Math., 190-191, 127-140 (2015) · Zbl 1316.05050 · doi:10.1016/j.dam.2015.04.006
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.