Equitable coloring of trees
type: Item
instance of: scholarly article
title: Equitable coloring of trees
zbMATH Open document ID: 0805.05027
author: Bor-Liang Chen
author: Ko-Wei Lih
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-01-26T00:00:00Z
review text: A graph \(G\) is said to be equitably \(k\)-colourable if the vertices of \(G\) can be partitioned into \(k\) independent sets \(V_ i\) such that \(\| V_ i | - | V_ j \| \leq 1\) for all \(i\) and \(j\). We regard a non-null tree \(T\) as a bipartite graph \(T(X,Y)\). The authors show that \(T\) is equitably \(k\)-colourable if and only if \[ k \geq 2 \quad \text{for} \quad \| X | - | Y \| \leq 1 \quad \text{and} \tag{i} \] \[ k \geq \max \Bigl \{3, \biggl \lceil \bigl( | T | + 1 \bigr) \bigl/ \biggl( \alpha \bigl(T - N(v) \bigr) + 2 \biggr) \biggr \rceil \Bigr\} \quad \text{for} \quad \| X | - | Y \|>1, \tag{ii} \] where \(v\) is an arbitrary vertex of maximum degree in \(T\) and \(\alpha(T-N(v))\) denotes the independence number of the subgraph of \(T\) obtained by deleting \(v\) and all its adjacent vertices.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 599863
zbMATH Keywords: equitable coloring
zbMATH Keywords: tree
zbMATH Keywords: bipartite graph
reviewed by: Jozef Fiamčík
MaRDI profile type: Publication
full work available at URL: jctb.1994.1032
OpenAlex ID: W1973336897
Wikidata QID: Q60060512
DOI: 10.1006/JCTB.1994.1032
DBLP publication ID: journals/jct/ChenL94
description: scientific article; zbMATH DE number 599863