Star chromatic number of triangle-free planar graphs
type: Item
instance of: scholarly article
title: Star chromatic number of triangle-free planar graphs
zbMATH Open document ID: 0796.05040
DOI: 10.1016/0893-9659(94)90057-4
published in: Applied Mathematics Letters
publication date: 1994-09-15T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 571532
zbMATH Keywords: star chromatic number
zbMATH Keywords: triangle-free planar graphs
author: Guo-Gang Gao
reviewed by: H. P. Yap
MaRDI profile type: Publication
full work available at URL: 0893-9659(94)90057-4
OpenAlex ID: W2063148437
cites work: Star chromatic number
cites work: Q5422499
cites work: A note on the star chromatic number
cites work: Grötzsch's theorem on 3-colorings
cites work: Star chromatic numbers and products of graphs
description: scientific article; zbMATH DE number 571532