Star chromatic number of triangle-free planar graphs
Let \(k\) and \(d\) be positive integers such that \(k \geq 2d\). A \((k,d)\)- colouring of a graph \(G=(V,E)\) is a mapping \(\varphi:V \to \{0,1, \dots,k-1\}\) such that for any edge \(xy\) of \(G\), \(| \varphi (x)- \varphi (y) |_ k \geq d\), where \(| z |_ k = \min (| z |,k-| z |)\). The star chromatic number of \(G\), denoted by \(\chi^* (G)\), is defined as \[ \chi^* (G)= \inf \left\{ {k \over d} :G \text{ has a } (k,d) \text{-colouring} \right\}. \] One of the properties of \(\chi^*(G)\) obtained earlier by A. Vince (1988) as well as J. A. Bondy and P. Hall (1990) is as follows: For any graph \(G\), \(\chi(G)-1<\chi^*(G)\leq\chi(G)\), i.e. \(\chi (G) = \lceil \chi^* (G) \rceil\). In this paper the author constructs an infinite family of triangle-free planar graphs \(G\) such that \(\chi^* (G)=3\). Note that (i) H. Grötzsch (1959) and B. Grünbaum (1963) had proved that for any triangle-free planar graph \(G\), \(\chi (G) \leq 3\); (ii) several classes of triangle-free planar graphs \(G\) such that \(\chi^* (G)<3\) had been obtained by several authors earlier.
scientific article; zbMATH DE number 571532