Can I read A List Analogue of Equitable Coloring on EtoBox?

A List Analogue of Equitable Coloring by A. V. Kostochka; M. J. Pelsmajer; D. B. West is a Computer Science article available to read on EtoBox.

What is A List Analogue of Equitable Coloring about?

## 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 $\lceil n (G)/k \rceil$ vertices. A graph is __equitably k‐choosable__ if such a coloring exists whenever the lists all have size __k__. We prove that __G__ is equitably __k__‐choosable when $k \ge {\rm max} \{ {\Delta (G),n(G)/2}\}$ unless __G__ contains $K\_{k+1}$ or __k__ is odd and $G=K\_{k,k}$. For forests, the threshold improves to $k \ge 1+\Delta (G)/2$. If __G__ is a 2‐degenerate graph (given __k__ ≥ 5) or a connected interval graph (other than $K\_{k+1}$), then __G__ is equitably __k__‐choosable when $k\ge \Delta(G)$. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 166–177, 2003

Who reads A List Analogue of Equitable Coloring?

Author

A. V. Kostochka; M. J. Pelsmajer; D. B. West

Publisher

John Wiley and Sons; Wiley (John Wiley & Sons); John Wiley & Sons Inc.; Wiley (ISSN 0364-9024)

Published

2003

Language

EN

Field

Computer Science (Physical Sciences)