On graphs double-critical with respect to the colouring number

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

2011-08-04

arxiv.org/abs/1108.1036v1

Mathematics

Combinatorics

IMADA-preprint-math, 15 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On graphs double-critical with respect to the colouring number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On graphs double-critical with respect to the colouring number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On graphs double-critical with respect to the colouring number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-14077