On graphs double-critical with respect to the colouring number

Anders Sune Pedersen; Matthias Kriesell

On graphs double-critical with respect to the colouring number

Department of Clinical Medicine - Center of Functionally Integrative Neuroscience

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

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.

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

Cite this

@article{058d41e8854845a682ad831c1b6a7d7f,

title = "On graphs double-critical with respect to the colouring number",

abstract = "The colouring number col(G) of a graph $G$ is the smallestinteger k for which there is an ordering of the vertices of G suchthat when removing the vertices of G in the specified order novertex of degree more than k-1 in the remaining graph is removed atany step. An edge e of a graph G is said to bedouble-col-critical if the colouring number of G-V(e) isat most the colouring number of G minus 2. A connected graph Gis said to be double-col-critical if each edge of G isdouble-col-critical. We characterise the double-col-criticalgraphs with colouring number at most 5. In addition, we prove thatevery 4-col-critical non-complete graph has at most half of itsedges being double-col-critical, and that the extremal graphs areprecisely the odd wheels on at least six vertices. We observe that forany integer k greater than 4 and any positive number \epsilon,there is a k-col-critical graph with the ratio ofdouble-col-critical edges between 1- \epsilon and 1.",

keywords = "graph colouring, graph characterizations, degenerate graphs, colouring number, double-critical graphs",

author = "Pedersen, {Anders Sune} and Matthias Kriesell",

year = "2015",

language = "English",

volume = "172",

pages = "49",

journal = "Discrete Mathematics and Theoretical Computer Science (Online Edition)",

issn = "1365-8050",

publisher = "D M T C S",

}

TY - JOUR

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

AU - Pedersen, Anders Sune

AU - Kriesell, Matthias

PY - 2015

Y1 - 2015

N2 - The colouring number col(G) of a graph $G$ is the smallestinteger k for which there is an ordering of the vertices of G suchthat when removing the vertices of G in the specified order novertex of degree more than k-1 in the remaining graph is removed atany step. An edge e of a graph G is said to bedouble-col-critical if the colouring number of G-V(e) isat most the colouring number of G minus 2. A connected graph Gis said to be double-col-critical if each edge of G isdouble-col-critical. We characterise the double-col-criticalgraphs with colouring number at most 5. In addition, we prove thatevery 4-col-critical non-complete graph has at most half of itsedges being double-col-critical, and that the extremal graphs areprecisely the odd wheels on at least six vertices. We observe that forany integer k greater than 4 and any positive number \epsilon,there is a k-col-critical graph with the ratio ofdouble-col-critical edges between 1- \epsilon and 1.

AB - The colouring number col(G) of a graph $G$ is the smallestinteger k for which there is an ordering of the vertices of G suchthat when removing the vertices of G in the specified order novertex of degree more than k-1 in the remaining graph is removed atany step. An edge e of a graph G is said to bedouble-col-critical if the colouring number of G-V(e) isat most the colouring number of G minus 2. A connected graph Gis said to be double-col-critical if each edge of G isdouble-col-critical. We characterise the double-col-criticalgraphs with colouring number at most 5. In addition, we prove thatevery 4-col-critical non-complete graph has at most half of itsedges being double-col-critical, and that the extremal graphs areprecisely the odd wheels on at least six vertices. We observe that forany integer k greater than 4 and any positive number \epsilon,there is a k-col-critical graph with the ratio ofdouble-col-critical edges between 1- \epsilon and 1.

KW - graph colouring

KW - graph characterizations

KW - degenerate graphs

KW - colouring number

KW - double-critical graphs

M3 - Journal article

SN - 1365-8050

VL - 172

SP - 49

JO - Discrete Mathematics and Theoretical Computer Science (Online Edition)

JF - Discrete Mathematics and Theoretical Computer Science (Online Edition)

ER -