Brooks-type theorem for r-hued coloring of graphs

An r-hued coloring of a simple graph G is a proper coloring of its vertices such that every vertex v is adjacent to at least min{r,deg(v)} differently colored vertices. The minimum number of colors needed for an r-hued coloring of a graph G, the r-hued chromatic number, is denoted by χr(G). In this...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2023-06, Vol.332, p.129-134
Main Authors: Jendrol’, Stanislav, Onderko, Alfréd
Format: Article
Language:English
Subjects:
[formula omitted]-hued chromatic number
[formula omitted]-hued coloring
Bipartite graph
Dynamic coloring
Vertex-coloring
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An r-hued coloring of a simple graph G is a proper coloring of its vertices such that every vertex v is adjacent to at least min{r,deg(v)} differently colored vertices. The minimum number of colors needed for an r-hued coloring of a graph G, the r-hued chromatic number, is denoted by χr(G). In this note we show that χr(G)≤(r−1)(Δ(G)+1)+2, for every simple graph G and every r≥2, which in the case when r
ISSN:0166-218X
DOI:10.1016/j.dam.2023.02.008