On the dynamic coloring of graphs

DOI10.1016/J.DAM.2010.10.012MaRDI QIDQ617650zbMATH OpenOpenAlexFDO

Authors Meysam Alishahi

Publication date 21 January 2011

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

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

zbMATH Keywords

total dominating setdynamic chromatic numberhypergraph coloringdynamic list chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.

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; zbMATH DE number 5901911
• On the list dynamic coloring of graphs
• scientific article; zbMATH DE number 6850309
• Dynamic graph coloring
• Dynamic graph coloring

Cites work

• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 2197944 (Why is no real title available?)
• Conditional colorings of graphs
• Dynamic list coloring of bipartite graphs
• Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen
• Hypergraph colouring and the Lovász local lemma
• Kneser's conjecture, chromatic number, and homotopy
• On the list dynamic coloring of graphs
• The Even Cycle Problem for Directed Graphs
• The dynamic coloring numbers of pseudo-Halin graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(49)

• On proper colorings of hypergraphs
• Dynamic list coloring of 1-planar graphs
• Element deletion changes in dynamic coloring of graphs
• Dynamic chromatic number of unicyclic graphs and bicyclic graphs
• Bounds on the dynamic chromatic number of a graph in terms of its chromatic number
• On the list dynamic coloring of graphs
• \(r\)-dynamic coloring of the corona product of graphs
• Adynamic coloring of graphs
• Dynamic coloring of graphs having no \(K_5\) minor
• On \(r\)-dynamic coloring of graphs
• The structure and the list 3-dynamic coloring of outer-1-planar graphs
• Dynamic coloring on restricted graph classes
• On dynamic coloring for planar graphs and graphs of higher genus
• On dynamic coloring of certain cycle-related graphs
• On \(r\)-hued colorings of graphs without short induced paths
• Linear list r-hued coloring of sparse graphs
• On the \(r\)-dynamic coloring of the direct product of a path and a \(k\)-subdivision of a star graph
• On \(r\)-hued coloring of corona product of some graphs
• On r- dynamic coloring of the family of bistar graphs
• The $r$-dynamic edge coloring of a closed helm graph
• Dynamic chromatic number of regular graphs
• scientific article; zbMATH DE number 6850309 (Why is no real title available?)
• Deterministic graph coloring in the streaming model
• On the difference between chromatic number and dynamic chromatic number of graphs
• Colored pebble motion on graphs (extended abstract)
• A MODEL OF GRAPH COLORING DYNAMICS WITH ATTENTION WAVES AND STRATEGIC WAITING
• A counterexample to montgomery's conjecture on dynamic colourings of regular graphs
• Dynamic coloring and list dynamic coloring of planar graphs
• scientific article; zbMATH DE number 6383853 (Why is no real title available?)
• scientific article; zbMATH DE number 5901911 (Why is no real title available?)
• 3-dynamic coloring and list 3-dynamic coloring of \(K_{1, 3}\)-free graphs
• scientific article; zbMATH DE number 2197944 (Why is no real title available?)
• The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
• On the dynamic coloring of Cartesian product graphs
• Graph \(r\)-hued colorings -- a survey
• 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
• On \(r\)-dynamic coloring of grids
• The dynamic coloring numbers of pseudo-Halin graphs
• On r− dynamic coloring of the gear graph families
• On \(r\)-dynamic chromatic number of graphs
• Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers
• An analog of Brooks' theorem for dynamic colorings
• Dynamic proper colorings of a graph
• Eternal coloring of a graph
• List dynamic 4-coloring of planar graphs
• Weak dynamic coloring of planar graphs

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)