## Abstract

A (k, r)-coloring of a graph G is a proper k-vertex coloring of G such that the neighbors of each vertex of degree d will receive at least min{d, r} different colors. The r-hued chromatic number, denoted by χ_{r}(G), is the smallest integer k for which a graph G has a (k, r)-coloring. Let f(r)=r+3 if 1 ≤ r ≤ 2, f(r)=r+5 if 3 ≤ r ≤ 7 and f(r)=⌊3r/2⌋+1 if r ≥ 8. In [Discrete Math., 315-316 (2014) 47-52], an extended conjecture of Wegner is proposed that if G is planar, then χ_{r}(G) ≤ f(r); and this conjecture was verified for K_{4}-minor free graphs. For an integer n ≥ 4, let K_{4}(n) be the set of all subdivisions of K_{4} on n vertices. We obtain decompositions of K_{4}(n)-minor free graphs with n ∈ {5, 6, 7}. The decompositions are applied to show that if G is a K_{4}(7)-minor free graph, then χ_{r}(G) ≤ f(r) if and only if G is not isomorphic to K_{6}.

Original language | English (US) |
---|---|

Article number | 125206 |

Journal | Applied Mathematics and Computation |

Volume | 384 |

DOIs | |

State | Published - Nov 1 2020 |

## Keywords

- (k, r)-coloring
- Coloring
- Decompositions
- Graph minor
- r-hued list coloring

## ASJC Scopus subject areas

- Computational Mathematics
- Applied Mathematics

## Fingerprint

Dive into the research topics of 'Decomposition and r-hued Coloring of K_{4}(7)-minor free graphs'. Together they form a unique fingerprint.