Opuscula Math. 45, no. 1 (2025), 103-111
https://doi.org/10.7494/OpMath.2025.45.1.103
Opuscula Mathematica
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.
- 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).
- 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
- 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
- B. Mohar, C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, 2001.
- 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
- J. Petersen, Die Theorie der regulären Graphs, Acta Math. 15 (1891), 193-220. https://doi.org/10.1007/bf02392606
- 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
- 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
- W.T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 2 (1946), 98-101. https://doi.org/10.1112/jlms/s1-21.2.98
- M. Voigt, private communication, 2024.
- H. Whitney, \(2\)-isomorphic graphs, Amer. J. Math. 55 (1933), 245-254. https://doi.org/10.2307/2371127
- 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
- Communicated by Andrzej Żak.
- Received: 2024-07-01.
- Revised: 2024-10-10.
- Accepted: 2024-10-25.
- Published online: 2024-12-20.
