## Kriesell, Matthias and Pedersen, Anders - On graphs double-critical with respect to the colouring number

dmtcs:2129 - Discrete Mathematics & Theoretical Computer Science, September 9, 2015, Vol. 17 no.2
On graphs double-critical with respect to the colouring number

Authors: Kriesell, Matthias and Pedersen, Anders

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 <i>double</i>-col-<i>critical</i> 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 <i>double</i>-col-<i>critical</i> 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.

Source : oai:HAL:hal-01349043v1
Volume: Vol. 17 no.2
Section: Graph Theory
Published on: September 9, 2015
Submitted on: October 21, 2012
Keywords: graph characterizations,graph colouring,degenerate graphs,colouring number,double-critical graphs,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]