✦ LIBER ✦

Equitable Coloring of Trees

✍ Scribed by B.L. Chen; K.W. Lih

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 224 KB
Volume: 61
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1994.1032

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is equitably (k)-colorable if its vertices can be partitioned into (k) independent sets of as near equal sizes as possible. Regarding a non-null tree (T) as a bipartite graph (T(X, Y)), we show that (T) is equitably (k)-colorable if and only if (i) (k \geqslant 2) when ||(X|-| Y|| \leqslant 1); (ii) (k \geqslant \max {3, \Gamma(|T|+1) /(\alpha(T-N[v])+2)\rceil}) when ||(X|-| Y||) (>1). In case (ii), (v) is an arbitrary vertex of maximum degree in (T) and the number (x(T-N[v])) denotes the independence number of the subgraph of (T) obtained by deleting (v) and all its adjacent vertices. 1994 Academic Press, Inc.

📜 SIMILAR VOLUMES

A list analogue of equitable coloring

✍ A. V. Kostochka; M. J. Pelsmajer; D. B. West 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB

## Abstract Given lists of available colors assigned to the vertices of a graph __G__, a __list coloring__ is a proper coloring of __G__ such that the color on each vertex is chosen from its list. If the lists all have size __k__, then a list coloring is __equitable__ if each color appears on at mo

Equitable list coloring and treewidth

✍ Michael J. Pelsmajer 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

Equitable Coloring and the Maximum Degre

Equitable Coloring and the Maximum Degree

✍ Bor-Liang Chen; Ko-Wei Lih; Pou-Lin Wu 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 184 KB

Let \(\Delta(G)\) denote the maximum degree of a graph \(G\). The equitable \(\Delta\)-coloring conjecture asserts that a connected graph \(G\) is equitably \(\Delta(G)\)-colorable if it is different from \(K_{m}, C_{2 m+1}\) and \(K_{2 m+1,2 m+1}\) for all \(m \geqslant 1\). This conjecture is esta

Edge-Coloring Partialk-Trees

✍ Xiao Zhou; Shin-ichi Nakano; Takao Nishizeki 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 278 KB

Many combinatorial problems can be efficiently solved for partial k-trees graphs . of treewidth bounded by k . The edge-coloring problem is one of the well-known combinatorial problems for which no efficient algorithms were previously known, except a polynomial-time algorithm of very high complexity

Equitable list-coloring for graphs of ma

Equitable list-coloring for graphs of maximum degree 3

✍ Michael J. Pelsmajer 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

## Abstract Given lists of available colors assigned to the vertices of a graph __G__, a list coloring is a proper coloring of __G__ such that the color on each vertex is chosen from its list. If the lists all have size __k__, then a list coloring is equitable if each color appears on at most ⌈|__V

Equitable edge-colorings of simple graph

Equitable edge-colorings of simple graphs

✍ Xia Zhang; Guizhen Liu 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 199 KB

An edge-coloring of a graph G is equitable if, for each v ∈ V (G), the number of edges colored with any one color incident with v differs from the number of edges colored with any other color incident with v by at most one. A new sufficient condition for equitable edge-colorings of simple graphs is