|
Zapiski Nauchnykh Seminarov POMI, 2010, Volume 381, Pages 47–77
(Mi znsl3852)
|
|
|
|
This article is cited in 6 scientific papers (total 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.
Received: 29.10.2010
Citation:
D. V. Karpov, “Dynamic proper vertex colorings of the graph”, Combinatorics and graph theory. Part II, Zap. Nauchn. Sem. POMI, 381, POMI, St. Petersburg, 2010, 47–77; J. Math. Sci. (N. Y.), 179:5 (2011), 601–615
Linking options:
https://www.mathnet.ru/eng/znsl3852 https://www.mathnet.ru/eng/znsl/v381/p47
|
Statistics & downloads: |
Abstract page: | 405 | Full-text PDF : | 135 | References: | 51 |
|