Indexed by:
Abstract:
The weak r-coloring numbers wcol(r) (G) of a graph G were introduced by the first two authors as a generalization of the usual coloring number col(G), and have since found interesting theoretical and algorithmic applications. This has motivated researchers to establish strong bounds on these parameters for various classes of graphs. Let G(p) denote the pth power of G. We show that, all integers p > 0 and Delta >= 3 and graphs G with Delta(G) <= Delta satisfy col(G(p)) is an element of O(p center dot wcol left perpendicular/2right perpendicular(G)(Delta - 1)left perpendicularp/2right perpendicular; for fixed tree width or fixed genus the ratio between this upper bound and worst case lower bounds is polynomial in p. For the square of graphs G, we also show that, if the maximum average degree 2k - 2 < mad(G) <= 2k, then col(G(2)) <= (2k - 1)Delta(G) + 2k + 1. (C) 2019 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
DISCRETE MATHEMATICS
ISSN: 0012-365X
Year: 2020
Issue: 6
Volume: 343
0 . 8 7
JCR@2020
0 . 7 0 0
JCR@2023
ESI Discipline: MATHEMATICS;
ESI HC Threshold:50
JCR Journal Grade:3
CAS Journal Grade:3
Cited Count:
SCOPUS Cited Count: 2
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: