On graphs double-critical with respect to the colouring number
Matthias Kriesell, Anders Sune Pedersen
Abstract
The colouring number col(G) of
a
graph G is the smallest integer k for which
there
is an ordering of the vertices of G such that when
removing
the vertices of G in the specified order no vertex of
degree
more than k-1 in the remaining graph is removed at any
step.
An edge e of a graph G is said to be
&em;double-col-critical
if
the colouring number of G-V(e) is at most the colouring
number
of G minus 2. A connected graph
G is said to be double-col-critical
if each edge of
G is double-col-critical.
We
characterise the double-col-critical
graphs
with colouring number at most 5. In addition, we prove
that
every 4-col-critical
non-complete graph has at most half
of its edges being double-col-critical,
and
that the extremal graphs are precisely the odd wheels on at least six
vertices.
We observe that for any integer k greater than
4
and any positive number ε, there is a
k-col-critical graph
with the ratio of double-col-critical
edges
between 1- ε and 1.
Full Text: PDF