Hardness of computing clique number and chromatic number for cayley graphs
| Speaker: | Brendan Rooney |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5479 |
Abstract:
Computing
the
clique
number
and
chromatic
number
of
a
general
graph
are
well-known
to
be
NP-Hard
problems.
Codenotti
et
al.
(Bruno
Codenotti,
Ivan
Gerace,
and
Sebastiano
Vigna.
Hardness
results
and
spectral
techniques
for
combinatorial
problems
on
circulant
graphs.
Linear
Algebra
Appl.,
285(1-3):
123--142,
1998)
showed
that
computing
clique
number
and
chromatic
number
are
still
NP-Hard
problems
for
the
class
of
circulant
graphs.
This
result
demonstrates
that
the
assumption
of
vertex
transitivity
does
not
make
computing
clique
number
or
chromatic
number
easier.
It
also
raises
the
question
of
whether
there
are
classes
of
Cayley
graphs
for
which
these
problems
are
easy
to
solve.
We
outline
a
proof
that
computing
clique
number
and
chromatic
number
are
NP-Hard
for
the
class
of
Cayley
graphs
for
the
groups
$G^n$,
where
$G$
is
any
fixed
finite
group.
In
particular,
this
shows
that
these
problems
are
NP-Hard
for
cubelike
graphs.
Our
method
brings
together:
a
construction
for
embedding
graphs
in
Cayley
graphs;
quotients
of
groups;
quotients
of
graphs;
and,
Goppa
codes.