Critical graphs for the chromatic edge-stability number

Abstract: The chromatic edge-stability number

{m e s}_{c h i} (G)

of a graph

G

is the minimum number of edges whose removal results in a spanning subgraph

G^{'}

with

c h i (G^{'}) = c h i (G) - 1

. Edge-stability critical graphs are introduced as the graphs

G

with the property that

{m e s}_{c h i} (G - e) < {m e s}_{c h i} (G)

holds for every edge

e i n E (G)

. If

G

is an edge-stability critical graph with

c h i (G) = k

and

{m e s}_{c h i} (G) = e l l

, then

G

is

(k, e l l)

-critical. Graphs which are

(3, 2)

-critical and contain at most four odd cycles are classified. It is also proved that the problem of deciding whether a graph

G

has

c h i (G) = k

and is critical for the chromatic number can be reduced in polynomial time to the problem of deciding whether a graph is

(k, 2)

-critical.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: Critical graphs for the chromatic edge-stability number