Note on robust coloring of planar graphs

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