Title: A generation theorem for near-bipartite bricks
| Speaker: | Nishad Kothari |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
It
is
well-known
that
all
3-connected
graphs
may
be
generated
from
K4
by
means
of
two
operations:
"edge
addition"
and
"vertex
expansion".
(However,
to
do
so,
one
must
allow
parallel
edges.)
We
will
discuss
similar
results
for
a
special
class
of
3-connected
graphs
called
'bricks',
which
play
a
central
role
in
matching
theory.
A
3-connected
graph
G
is
a
brick
if
G
-
{u,v}
has
a
perfect
matching
for
each
pair
of
vertices
u
and
v.
It
was
shown
by
Carvalho,
Lucchesi
and
Murty
that
all
bricks
may
be
generated
from
K4,
the
triangular
prism
and
the
Petersen
graph
by
means
of
four
operations.
We
prove
a
generation
theorem
for
a
special
class
of
bricks;
a
brick
G
is
near-bipartite
if
it
has
two
edges
e
and
f
such
that
G
-
{e,f}
is
bipartite
and
matching
covered.
In
particular,
we
show
that
all
near-bipartite
bricks
may
be
generated
from
K4
and
the
triangular
prism
by
means
of
three
operations.