Adynamic coloring of graphs

For a graph G with at least one vertex with independent neighborhood, an adynamic coloring of G is a proper vertex coloring of G such that there exists at least one vertex of degree at least 2 whose all neighbors have the same color. We explore basic properties of adynamic colorings and their relati...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2020-09, Vol.284, p.224-233
Main Authors: Šurimová, Mária, Lužar, Borut, Madaras, Tomáš
Format: Article
Language:English
Subjects:
Adynamic coloring
Dynamic coloring
Four color problem
Graph coloring
Graphs
Planar graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For a graph G with at least one vertex with independent neighborhood, an adynamic coloring of G is a proper vertex coloring of G such that there exists at least one vertex of degree at least 2 whose all neighbors have the same color. We explore basic properties of adynamic colorings and their relations to proper and dynamic colorings. We also establish a number of results for planar graphs; in particular, we extend the Four Color Theorem and Grötzsch’s Theorem to adynamic coloring. Finally, we prove that triangle-free graphs with maximum degree 3 are adynamically 3-colorable, which is surprisingly not true for graphs of higher maximum degrees.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2020.03.038