Opuscula Mathematica
Opuscula Math. 45, no. 1 (2025), 103-111

Note on robust coloring of planar graphs

František Kardoš
Borut Lužar
Roman Soták
Abstract. We consider the robust chromatic number \(\chi_1(G)\) of planar graphs \(G\) and show that there exists an infinite family of planar graphs \(G\) with \(\chi_1(G) = 3\), thus solving a recent problem of Bacsó et al. from [The robust chromatic number of graphs, Graphs Combin. 40 (2024), #89].
Keywords: robust coloring, robust chromatic number, Tutte graph, planar graph.
Mathematics Subject Classification: 05C15, 05C10.
Full text (pdf)
References ▼
  1. [1] G. Bacsó, C. Bujtás, B. Patkós, Z. Tuza, M. Vizer, The robust chromatic number of certain graph classes, arXiv:2305.01927 [math.CO], (2023).
  2. [2] G. Bacsó, B. Patkós, Z. Tuza, M. Vizer, The robust chromatic number of graphs, Graphs Combin. 40 (2024), #89. https://doi.org/10.1007/s00373-024-02817-1
  3. [3] A. Kemnitz, M. Voigt, A note on non-4-list colorable planar graphs, Electron. J. Combin. 25 (2018), #P2.46. https://doi.org/10.37236/7320
  4. [4] B. Mohar, C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, 2001.
  5. [5] B. Patkós, Z. Tuza, M. Vizer, Extremal graph theoretic questions for \(q\)-ary vectors, Graphs Combin. 40 (2024), #57. https://doi.org/10.1007/s00373-024-02787-4
  6. [6] J. Petersen, Die Theorie der regulären Graphs, Acta Math. 15 (1891), 193-220. https://doi.org/10.1007/bf02392606
  7. [7] M. Rosenfeld, The number of cycles in 2-factors of cubic graphs, Discrete Math. 84 (1990), 285-294. https://doi.org/10.1016/0012-365x(90)90133-3
  8. [8] C. Thomassen, Five-coloring graphs on the torus, J. Combin. Theory Ser. B, 62 (1994) 1, 11-33. https://doi.org/10.1006/jctb.1994.1052
  9. [9] W.T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 2 (1946), 98-101. https://doi.org/10.1112/jlms/s1-21.2.98
  10. [10] M. Voigt, private communication, 2024.
  11. [11] H. Whitney, \(2\)-isomorphic graphs, Amer. J. Math. 55 (1933), 245-254. https://doi.org/10.2307/2371127
About the authors ▼
František Kardoš
https://orcid.org/0000-0002-9826-2927
University of Bordeaux, CNRS, LaBRI, Talence, France; Comenius University, Faculty of Mathematics, Physics and Informatics, Bratislava, Slovakia
Borut Lužar (corresponding author)
https://orcid.org/0000-0002-8356-8827
Faculty of Information Studies, Novo Mesto, Slovenia; Rudolfovo Institute, Novo Mesto, Slovenia
Roman Soták
https://orcid.org/0000-0002-0667-0019
Pavol Jozef Šafárik University, Faculty of Science, Institute of Mathematics, Košice, Slovakia
About the article ▼
Communicated by Andrzej Żak.
Received: 2024-07-01.
Revised: 2024-10-10.
Accepted: 2024-10-25.
Published online: 2024-12-20.
Cite this article as ▼
František Kardoš, Borut Lužar, Roman Soták, Note on robust coloring of planar graphs, Opuscula Math. 45, no. 1 (2025), 103-111, https://doi.org/10.7494/OpMath.2025.45.1.103.
Download this article's citation as: