TY - JOUR

T1 - Dynamic proper colorings of a graph

AU - Karpov, D. V.

PY - 2011/12/1

Y1 - 2011/12/1

N2 - A subdivision of complete graph Kn is any graph that can be obtained from Kn by replacing edges of Kn by chains of two edges (every such chain adds to the graph a new vertex of degree 2). Let G be a connected graph with maximal vertex degree d, d ≥ 8. We prove that there is a proper dynamic vertex coloring of G with d colors iff G is distinct from Kd+1 and its subdivisions. Bibliography: 7 titles.

AB - A subdivision of complete graph Kn is any graph that can be obtained from Kn by replacing edges of Kn by chains of two edges (every such chain adds to the graph a new vertex of degree 2). Let G be a connected graph with maximal vertex degree d, d ≥ 8. We prove that there is a proper dynamic vertex coloring of G with d colors iff G is distinct from Kd+1 and its subdivisions. Bibliography: 7 titles.

UR - http://www.scopus.com/inward/record.url?scp=83055186785&partnerID=8YFLogxK

U2 - 10.1007/s10958-011-0612-3

DO - 10.1007/s10958-011-0612-3

M3 - Article

AN - SCOPUS:83055186785

VL - 179

SP - 601

EP - 615

JO - Journal of Mathematical Sciences

JF - Journal of Mathematical Sciences

SN - 1072-3374

IS - 5

ER -