Every signed planar graph of girth 5 has circular chromatic number strictly less than 4

Jiaao Li¹ ; Xueliang Li² ; Zhiqian Wang²

¹School of Mathematical Sciences and LPMC, Nankai University
²Center for Combinatorics and LPMC, Nankai University

The electronic journal of combinatorics, Tome 32 (2025) no. 2

Résumé

For a real number $r\ge 2$, a circular $r$-colouring of a signed graph $(G, \sigma)$ is a mapping $c: V(G)\to [0, r)$ such that $|c(x)-c(y)|\in [1,r-1]$ for each positive edge $xy$ and $|c(x)-c(y)|\in [0,r/2-1]\cup [r/2+1,r)$ for each negative edge $xy$. This concept is recently introduced by Naserasr, Wang, and Zhu in 2021, and they show that for any $\varepsilon>0$, there exist signed planar bipartite graphs (of girth 4) which are not circular $(4-\varepsilon)$-colourable. In this paper, we prove that for each signed planar graph $(G, \sigma)$ of girth at least $5$, there exists a real number $\varepsilon=\varepsilon(G,\sigma)>0$ such that $(G, \sigma)$ is circular $(4-\varepsilon)$-colorable. Our proof utilizes a Thomassen-type inductive argument on the dual version in terms of circular flows, which is motivated by a result of Richter, Thomassen, and Younger (2016) on group connectivity of $5$-edge-connected planar graphs.

Détail

DOI : 10.37236/12168

Classification : 05C22, 05C10, 05C15
Mots-clés : circular \(r\)-colouring, Thomassen-type inductive argument