## 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

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 \epsilon,

there is a k-col-critical graph with the ratio of

double-col-critical edges between 1- \epsilon and 1.

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

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 \epsilon,

there is a k-col-critical graph with the ratio of

double-col-critical edges between 1- \epsilon and 1.

Original language | English |
---|---|

Journal | Discrete Mathematics and Theoretical Computer Science (Online Edition) |

Volume | 172 |

Pages (from-to) | 49 |

Number of pages | 62 |

ISSN | 1365-8050 |

Publication status | Published - 2015 |