[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Packing colorings of subcubic outerplanar graphs

  • Published:
Aequationes mathematicae Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

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)

    Article  MathSciNet  Google Scholar 

  2. Argiroffo, G., Nasini, G., Torres, P.: The packing coloring problem for lobsters and partner limited graphs. Discrete Appl. Math. 164, 373–382 (2014)

    Article  MathSciNet  Google Scholar 

  3. Balogh, J., Kostochka, A., Liu, X.: Packing chromatic number of subcubic graphs. Discrete Math. 341, 474–483 (2018)

    Article  MathSciNet  Google Scholar 

  4. Balogh, J., Kostochka, A., Liu, X.: Packing chromatic number of subdivisions of cubic graphs. Graphs Combin. 35(2019), 513–537 (2019)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  6. Brešar, B., Ferme, J.: An infinite family of subcubic graphs with unbounded packing chromatic number. Discrete Math. 341, 2337–2342 (2018)

    Article  MathSciNet  Google Scholar 

  7. 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)

    Article  MathSciNet  Google Scholar 

  8. Brešar, B., Klavžar, S., Rall, D.F.: Packing chromatic number of base-3 Sierpiński graphs. Graphs Combin. 32, 1313–1327 (2016)

    Article  MathSciNet  Google Scholar 

  9. Brešar, B., Klavžar, S., Rall, D.F., Wash, K.: Packing chromatic number under local changes in a graph. Discrete Math. 340, 1110–1115 (2017)

    Article  MathSciNet  Google Scholar 

  10. Brešar, B., Klavžar, S., Rall, D.F., Wash, K.: Packing chromatic number, \((1,1,2,2)\)-colorings, and characterizing the Petersen graph. Aequ. Math. 91, 169–184 (2017)

    Article  MathSciNet  Google Scholar 

  11. Ekstein, J., Holub, P., Togni, O.: The packing coloring of distance graphs \(D(k, t)\). Discrete Appl. Math. 167, 100–106 (2014)

    Article  MathSciNet  Google Scholar 

  12. Fiala, J., Golovach, P.A.: Complexity of the packing coloring problem for trees. Discrete Appl. Math. 158, 771–778 (2010)

    Article  MathSciNet  Google Scholar 

  13. Fiala, J., Klavžar, S., Lidický, B.: The packing chromatic number of infinite product graphs. Eur. J. Combin. 30, 1101–1113 (2009)

    Article  MathSciNet  Google Scholar 

  14. Finbow, A., Rall, D.F.: On the packing chromatic number of some lattices. Discrete Appl. Math. 158, 1224–1228 (2010)

    Article  MathSciNet  Google Scholar 

  15. Gastineau, N., Togni, O.: \(S\)-packing colorings of cubic graphs. Discrete Math. 339, 2461–2470 (2016)

    Article  MathSciNet  Google Scholar 

  16. Gastineau, N., Holub, P., Togni, O.: On packing chromatic number of subcubic outerplanar graphs. Discrete Appl. Math. 255, 209–221 (2019)

    Article  MathSciNet  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  18. Jacobs, Y., Jonck, E., Joubert, E.J.: A lower bound for the packing chromatic number of the Cartesian product of cycles. Cent. Eur. J. Math. 11, 1344–1357 (2013)

    MathSciNet  MATH  Google Scholar 

  19. Korže, D., Vesel, A.: On the packing chromatic number of square and hexagonal lattice. Ars Math. Contemp. 7, 13–22 (2014)

    Article  MathSciNet  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  21. Lih, K.-W., Wang, W.-F.: Coloring the square of an outerplanar graph. Taiwan. J. Math. 10, 1015–1023 (2006)

    Article  MathSciNet  Google Scholar 

  22. Shao, Z., Vesel, A.: Modeling the packing coloring problem of graphs. Appl. Math. Model. 39, 3588–3595 (2015)

    Article  MathSciNet  Google Scholar 

  23. Sloper, C.: An eccentric coloring of trees. Australas. J. Combin. 29, 309–321 (2004)

    MathSciNet  MATH  Google Scholar 

  24. Soukal, R., Holub, P.: A note on packing chromatic number of the square lattice. Electron. J. Combin. 17, 447–468 (2010)

    Article  MathSciNet  Google Scholar 

  25. Togni, O.: On packing colorings of distance graphs. Discrete Appl. Math. 167, 280–289 (2014)

    Article  MathSciNet  Google Scholar 

  26. Torres, P., Valencia-Pabon, M.: The packing chromatic number of hypercubes. Discrete Appl. Math. 190–191, 127–140 (2015)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We are grateful to an anonymous referee for a careful reading of the initial version of the paper and for a number of suggestions that helped to improve the presentation. This work was performed with the financial support of the bilateral project “Distance-constrained and game colorings of graph products” (BI-FR/18-19-Proteus-011). B.B. acknowledges the financial support from the Slovenian Research Agency (research core Funding No. P1-0297, project Contemporary invariants in Graphs No. J1-9109, and project Contemporary and New Metric Concepts in Graph Theory No. J1-1693).

Author information

Authors and Affiliations

  1. Faculty of Natural Sciences and Mathematics, University of Maribor, Maribor, Slovenia

    Boštjan Brešar

  2. Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

    Boštjan Brešar

  3. Laboratoire LIB, Université de Bourgogne Franche-Comté, Dijon, France

    Nicolas Gastineau & Olivier Togni

Authors
  1. Boštjan Brešar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nicolas Gastineau
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Olivier Togni
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Boštjan Brešar.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Brešar, B., Gastineau, N. & Togni, O. Packing colorings of subcubic outerplanar graphs. Aequat. Math. 94, 945–967 (2020). https://doi.org/10.1007/s00010-020-00721-6

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00010-020-00721-6

Keywords

Mathematics Subject Classification

Search

Navigation