A note on the \(m\)-bounded chromatic number of a tree (Q685308)

The \(m\)-bounded chromatic number of a graph \(G\) is the smallest number of colors required for a proper coloring of \(G\) in which each color is used at most \(m\) times and is denoted by \(\chi_ m(G)\). In this paper a tree \(T\), that is a bipartite graph, is expressed as \(T(X,Y)\), with the two parts \(X\) and \(Y\) explicitly written out; further, \(\alpha(G)\) denotes the independence number of \(G\) and \(N(v)\) consists of all vertices adjacent to \(v\). The authors establish an exact formula for the \(m\)-bounded chromatic number of a tree, namely: if \(T=T(X,Y)\) is a tree and \(v\) is an arbitrary vertex of maximum degree, then (i) \(\chi_ m(T)=2\) when \(m \geq \max(| X |, | Y |)\); (ii) \(\chi_ m(T)=\max(3,\lceil| V(T)|/m \rceil,\lceil(| V(T)|-\alpha (T-N(v)))/m \rceil+1)\) otherwise.