Kittikorn Nakprasit
Department of Mathematics, University of Illinois at Urbana-Champaign

                Equitable colorings of k-degenerate graph

        In many applications of graph colorings the sizes of color
classes should not differ too much. A formalization of this requirement
is the notion of equitable coloring.
        An equitable coloring is a proper vertex coloring such that the
sizes of color classes differ by at most 1. Finding for a given $k$
whether a graph $G$ admits an equitable $k$-coloring is most likely an
NP-complete problem.
        A $d$-degenerate graph is a graph whose every subgraph  has
minimum
degree at most $d$.
        The main result of the talk is finding the minimum number
$l=l(d,\Delta)$ such that every $d$-degenerate graph with maximum degree
at most $\Delta$ admits an equitable $m$-coloring for every $m\geq l$ when
$\Delta\geq 27d$.To prove this, we show A polynomial-time approximation
algorithm for equitable coloring $d$-degenerate graphs.