Premium
Equitable list‐coloring for graphs of maximum degree 3
Author(s) -
Pelsmajer Michael J.
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20011
Subject(s) - combinatorics , list coloring , mathematics , complete coloring , fractional coloring , vertex (graph theory) , graph coloring , graph , edge coloring , discrete mathematics , greedy coloring , graph power , line graph
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 Δ( G ) = 3. We also show that every graph G is equitably k ‐choosable for k ≥ Δ( G )(Δ( G )−1)/2 + 2. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 1–8, 2004