On the dynamic coloring of graphs

DOI10.1016/J.DAM.2010.10.012zbMATH Open1203.05046arXiv0908.2543OpenAlexW2074480183MaRDI QIDQ617650FDOQ617650

Meysam Alishahi

Publication date: 21 January 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A dynamic coloring of a graph $G$ is a proper coloring such that for every vertex $vinV(G)$ of degree at least 2, the neighbors of $v$ receive at least 2 colors. In this paper we present some upper bounds for the dynamic chromatic number of graphs. In this regard, we shall show that there is a constant $c$ such that for every $k$-regular graph $G$, $ch{i}_d(G)leqchi(G)+clnk+1$. Also, we introduce an upper bound for the dynamic list chromatic number of regular graphs.

Full work available at URL: https://arxiv.org/abs/0908.2543

Recommendations

• Dynamic coloring of graphs
• On \(r\)-dynamic coloring of graphs
• Dynamic proper colorings of a graph
• On dynamic coloring of certain cycle-related graphs
• Dynamic coloring on restricted graph classes
• scientific article
• On the list dynamic coloring of graphs
• scientific article; zbMATH DE number 6850309
• Dynamic graph coloring
• Dynamic graph coloring

zbMATH Keywords

total dominating setdynamic chromatic numberhypergraph coloringdynamic list chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Kneser's conjecture, chromatic number, and homotopy
• Conditional colorings of graphs
• Title not available (Why is that?)
• Dynamic list coloring of bipartite graphs
• On the list dynamic coloring of graphs
• Hypergraph colouring and the Lovász local lemma
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen
• The Even Cycle Problem for Directed Graphs

Cited In (39)

• The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
• The $r$-dynamic edge coloring of a closed helm graph
• A MODEL OF GRAPH COLORING DYNAMICS WITH ATTENTION WAVES AND STRATEGIC WAITING
• 3-dynamic coloring and list 3-dynamic coloring of \(K_{1, 3}\)-free graphs
• Title not available (Why is that?)
• Element deletion changes in dynamic coloring of graphs
• On dynamic coloring for planar graphs and graphs of higher genus
• Title not available (Why is that?)
• The structure and the list 3-dynamic coloring of outer-1-planar graphs
• Dynamic coloring of graphs having no \(K_5\) minor
• On \(r\)-dynamic coloring of graphs
• On \(r\)-hued coloring of corona product of some graphs
• On the \(r\)-dynamic coloring of subdivision-edge coronas of a path
• On the \(r\)-dynamic coloring of the direct product of a path with either a complete graph or a wheel graph
• On the \(r\)-dynamic coloring of the direct product of a path with either a path or a cycle
• List \(r\)-hued chromatic number of graphs with bounded maximum average degrees
• Dynamic chromatic number of regular graphs
• Title not available (Why is that?)
• On \(r\)-dynamic chromatic number of graphs
• On \(r\)-hued colorings of graphs without short induced paths
• Title not available (Why is that?)
• Dynamic chromatic number of unicyclic graphs and bicyclic graphs
• Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers
• On r− dynamic coloring of the gear graph families
• Dynamic coloring on restricted graph classes
• Deterministic graph coloring in the streaming model
• Dynamic coloring and list dynamic coloring of planar graphs
• Colored pebble motion on graphs (extended abstract)
• On \(r\)-dynamic coloring of grids
• Adynamic coloring of graphs
• On r- dynamic coloring of the family of bistar graphs
• Graph \(r\)-hued colorings -- a survey
• List dynamic 4-coloring of planar graphs
• A counterexample to montgomery's conjecture on dynamic colourings of regular graphs
• Dynamic list coloring of 1-planar graphs
• Weak dynamic coloring of planar graphs
• Linear list r-hued coloring of sparse graphs
• r-Dynamic coloring of the corona product of graphs
• On the r-dynamic coloring of the direct product of a path and a k-subdivision of a star graph

This page was built for publication: On the dynamic coloring of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q617650)