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

On graphs double-critical with respect to the colouring number - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Institute of Mathematics - Technical University of Ilmenau 2 IMADA - Department of Mathematics and Computer Science Odense 3 Research Clinic on Gambling Disorders, Aarhus University Hospital

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-Ve\$ 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 : graph characterizations graph colouring degenerate graphs colouring number double-critical graphs

Autor: Matthias Kriesell - Anders Pedersen -

Fuente: https://hal.archives-ouvertes.fr/

DESCARGAR PDF