# On graphs double-critical with respect to the colouring number

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 $ε$, there is a $k$-col-critical graph with the ratio of double-col-critical edges between $1- ε$ and 1.
Keywords :
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.49-62

Littérature citée [15 références]

https://hal.inria.fr/hal-01349043
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 26 juillet 2016 - 16:41:36
Dernière modification le : jeudi 7 septembre 2017 - 01:03:50

### Fichier

2320-9766-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-01349043, version 1

### Citation

Matthias Kriesell, Anders Pedersen. On graphs double-critical with respect to the colouring number. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.49-62. 〈hal-01349043〉

### Métriques

Consultations de la notice

## 33

Téléchargements de fichiers