<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\magnification=1200
\hsize=4in
\overfullrule=0pt
\nopagenumbers
\noindent
%
%
{\bf Maria Axenovich}
%
%
\medskip
\noindent
%
%
{\bf A Note on Graph Coloring Extensions and List-Colorings}
%
%
\vskip 5mm
\noindent
%
%
%
%
Let $G$ be a graph with maximum degree $\Delta \geq 3$ not equal to $K_{\Delta +1}$ and let
$P$ be a subset of vertices with pairwise distance, $d(P)$, between them at least
$8$. Let each vertex $x$ be assigned  a list of colors of size $\Delta$ if $x\in V\setminus P$ and $1$ if $x\in P$.
We prove that it is possible to color $V(G)$ such that
adjacent vertices receive different colors and each vertex has a color from its list.
We show that $d(P)$ cannot be improved.
This generalization of Brooks' theorem answers the following question of Albertson positively:
If $G$ and $P$ are objects described above, can any coloring of $P$ in at most $\Delta$ colors
 be extended to a proper coloring of $G$ in at most $\Delta$ colors?

\bye
</pre></body></html>