RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2010 Volume 381, Pages 47–77 (Mi znsl3852)

This article is cited in 6 papers

Dynamic proper vertex colorings of the graph

D. V. Karpov

St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences, St. Petersburg, Russia

Abstract: Let a subdivision of the complete graph $K_n$ be any graph, which can be constructed from $K_n$ by substituting some edges of $K_n$ with chains of two edges (every such chain adds to a graph a new vertex of degree 2).
Let $d\ge8$, $G$ is a connected graph with maximal vertex degree $d$. We proof that there is a proper dynamic vertex coloring of $G$ with $d$ colors iff $G$ is distinct from $K_{d+1}$ and its subdivisions. Bibl. 7 titles.

Key words and phrases: proper coloring, dynamic coloring, Brooks' theorem.

UDC: 519.174.7

Received: 29.10.2010


 English version:
Journal of Mathematical Sciences (New York), 2011, 179:5, 601–615

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024