2011/08/04 by Matthias Kriesell, Kriesell, Matthias, Anders Sune Pedersen +1
Computer Science · Mathematics · #05C15 #05c75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C15 #msc:05c75
paper · pdf · doi:10.48550/arxiv.1108.1036
IMADA-preprint-math, 15 pages
arxiv created 2011/08/04 · openalex publication_date 2011/08/04 · arxiv updated 2011/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 r, there is a k-col-critical graph with the ratio of double-col-critical edges between 1- r and 1.