A note on the m-bounded chromatic number of a tree

DOI10.1006/EUJC.1993.1034MaRDI QIDQ685308zbMATH OpenOpenAlexFDO

Authors Bor-Liang Chen, Ko-Wei Lih

Publication date 17 October 1993

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/eujc.1993.1034

zbMATH Keywords

\(m\)-bounded chromatic numbercolorcoloringindependence numbermaximum degreetree

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Review text

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.

Recommendations

• Bounded vertex coloring of trees
• Bounded vertex colorings of graphs
• Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree
• \(B\)-chromatic number of cacti
• scientific article; zbMATH DE number 2014472

Cited in

(4)

• Locally boundedk-colorings of trees
• Exact values for theb-chromatic number of a power completek-ary tree
• Bounded vertex coloring of trees
• Equitable and m-bounded coloring of split graphs

This page was built for publication: A note on the \(m\)-bounded chromatic number of a tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685308)