Note on robust coloring of planar graphs

• Autorzy: Kardoš František , Lužar Borut , Soták Roman

Identyfikatory

DOI

10.7494/OpMath.2025.45.1.103

• Języki publikacji: EN

Abstrakty

EN

We consider the robust chromatic number χ1(G) of planar graphs G and show that there exists an infinite family of planar graphs G with χ1(G) = 3, thus solving a recent problem of Bacsó et al. from [The robust chromatic number of graphs, Graphs Combin. 40 (2024), #89].

Słowa kluczowe

EN

robust coloring; robust chromatic number; Tutte graph; planar graph

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2025
• Tom: Vol. 45, no. 1
• Strony: 103--111
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Kardoš František

• University of Bordeaux, CNRS, LaBRI, Talence, France
• Comenius University, Faculty of Mathematics, Physics and Informatics, Bratislava, Slovakia

• https://orcid.org/0000-0002-9826-2927

autor

Lužar Borut

• Faculty of Information Studies, Novo Mesto, Slovenia
• Rudolfovo Institute, Novo Mesto, Slovenia

• https://orcid.org/0000-0002-8356-8827

autor

Soták Roman

• Pavol Jozef Šafárik University, Faculty of Science, Košice, Slovakia

• https://orcid.org/0000-0002-0667-0019

Bibliografia

• [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] G. Bacsó, B. Patkós, Z. Tuza, M. Vizer, The robust chromatic number of graphs, Graphs Combin. 40 (2024), #89.
• [3] A. Kemnitz, M. Voigt, A note on non-4-list colorable planar graphs, Electron. J. Combin. 25 (2018), #P2.46.
• [4] B. Mohar, C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, 2001.
• [5] B. Patkós, Z. Tuza, M. Vizer, Extremal graph theoretic questions for q-ary vectors, Graphs Combin. 40 (2024), #57.
• [6] J. Petersen, Die Theorie der regulären Graphs, Acta Math. 15 (1891), 193–220.
• [7] M. Rosenfeld, The number of cycles in 2-factors of cubic graphs, Discrete Math. 84 (1990), 285–294.
• [8] C. Thomassen, Five-coloring graphs on the torus, J. Combin. Theory Ser. B, 62 (1994) 1, 11–33.
• [9] W.T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 2 (1946), 98–101.
• [10] M. Voigt, private communication, 2024.
• [11] H. Whitney, 2-isomorphic graphs, Amer. J. Math. 55 (1933), 245–254.