By Peter D. Johnson Jr.
Auburn University
Abstract:
Let k be a function from the vertices of a graph
into the non-negative integers. A
proper (t, k)-coloring of the graph is an assignment of
subsets of {1,...,t} to the vertices of the graph so that each vertex v
is assigned a set of cardinality k (v), and adjacent vertices are assigned
disjoint sets. Sometimes there is a
proper coloring, and sometimes there isn't.
There is a well known necessary condition for the existence of such a
coloring, a special case of something called Hall's condition: for every induced subgraph H of the
graph, t times the vertex independence number of the subgraph must be at
least as large as the sum of the values of k on the vertices of the subgraph.
For a fixed non-negative integer t,
this condition becomes a condition on the function kappa. The graph will be called Hall t-chromatic
if there is a proper (t, k)-coloring of the graph whenever Hall's
condition is satisfied--i.e., if the necessary condition for a proper coloring
is sufficient.
All graphs are Hall t-chromatic
for t = 0,1, or 2. A lot of
graphs are Hall t-chromatic for all t. Some rare graphs are Hall t-chromatic only for t =
0, 1, or 2. There is a great steaming
pile of open problems in this area.
March 31, 2005
At 3:30 in Wallace 430