✦ LIBER ✦

Equitable list coloring and treewidth

✍ Scribed by Michael J. Pelsmajer

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 143 KB
Volume: 61
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20373

No coin nor oath required. For personal study only.

✦ Synopsis

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(G)|/k⌉ vertices. A graph is equitably k ‐choosable if such a coloring exists whenever the lists all have size k. Kostochka, Pelsmajer, and West introduced this notion and conjectured that G is equitably k‐choosable for k>Δ(G). We prove this for graphs of treewidth w≤5 if also k≥3__w__−1. We also show that if G has treewidth w≥5, then G is equitably k‐choosable for k≥max{Δ(G)+w−4, 3__w__−1}. As a corollary, if G is chordal, then G is equitably k‐choosable for k≥3Δ(G)−4 when Δ(G)>2. © 2009 Wiley Periodicals, Inc. J Graph Theory

📜 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 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 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

On list-coloring outerplanar graphs

✍ Joan P. Hutchinson 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB

## Abstract We prove that a 2‐connected, outerplanar bipartite graph (respectively, outerplanar near‐triangulation) with a list of colors __L__ (__v__ ) for each vertex __v__ such that $|L(v)|\geq\min\{{\deg}(v),4\}$ (resp., $|L(v)|\geq{\min}\{{\deg}(v),5\}$) can be __L__‐list‐colored (except when

List circular coloring of trees and cycl

List circular coloring of trees and cycles

✍ André Raspaud; Xuding Zhu 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB

## Abstract Suppose __G__=(__V__, __E__) is a graph and __p__ ≥ 2__q__ are positive integers. A (__p__, __q__)‐coloring of __G__ is a mapping ϕ: __V__ → {0, 1, …, __p__‐1} such that for any edge __xy__ of __G__, __q__ ≤ |ϕ(__x__)‐ϕ(__y__)| ≤ __p__‐__q__. A color‐list is a mapping __L__: __V__ → $\c

On list coloring Steiner triple systems

✍ P. E. Haxell; M. Pei 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

## Abstract We study the list chromatic number of Steiner triple systems. We show that for every integer __s__ there exists __n__~0~=__n__~0~(__s__) such that every Steiner triple system on __n__ points STS(__n__) with __n__≥__n__~0~ has list chromatic number greater than __s__. We also show that t