Rigidity, Unique Vector Colorings, and Cores
| Speaker: | David Roberson |
|---|---|
| Affiliation: | Nanyang Technological University |
| Room: | Mathematics and Computer Building (MC) 5479 |
Abstract:
A
vector
$t$-coloring
of
a
graph
is
an
assignment
of
unit
vectors
to
the
vertices
of
the
graph
such
that
the
inner
product
of
vectors
assigned
to
adjacent
vertices
is
less
than
or
equal
to
$-1/(t-1)$.
The
vector
chromatic
number
of
a
graph
is
the
minimum
$t$
for
which
it
admits
a
vector
$t$-coloring.
An
$n$-coloring
of
a
graph
can
be
converted
to
a
vector
$n$-coloring
by
mapping
the
vertices
of
each
color
class
to
the
vertices
of
a
regular
$(n-1)$-simplex.
This
shows
that
the
vector
chromatic
number
is
always
at
most
the
chromatic
number,
but
it
can
sometimes
be
much
smaller.
In
this
talk
we
will
focus
on
finding
graphs
with
unique
(up
to
isometry)
optimal
vector
colorings.
Our
main
tool
for
finding
such
graphs
will
be
a
result
from
rigidity
theory.
We
will
also
investigate
vector
colorings
of
categorical
products
of
graphs.
In
particular,
we
consider
the
following
three
statements:
- If $G$ and $H$ are uniquely vector $t$-colorable, then the only vector $t$-colorings of $G \times H$ are the convex combinations of the vector $t$-colorings induced by the factors.
- If $G$ is uniquely vector $t$-colorable and $H$ has vector chromatic number greater than $t$, then $G \times H$ is uniquely vector $t$-colorable.
- The vector chromatic number of $G \times H$ is the minimum of the vector chromatic numbers of $G$ and $H$.
These are vector coloring analogs of three statements considered by Duffus, Sands, and Woodrow. In particular, (C) is a vector analog of Hedetniemi's conjecture. We prove (C) and prove (A) and (B) for 1-walk-regular graphs. Lastly, we discuss a surprising connection between unique vector colorability and cores (graphs which do not admit homomorphisms to any proper subgraph).