Decomposition and r-hued Coloring of K4(7)-minor free graphs

Ye Chen, Suohai Fan, Hong-Jian Lai, Huimin Song and Murong Xu

Applied Mathematics and Computation, 2020, vol. 384, issue C

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 K4-minor free graphs. For an integer n ≥ 4, let K4(n) be the set of all subdivisions of K4 on n vertices. We obtain decompositions of K4(n)-minor free graphs with n ∈ {5, 6, 7}. The decompositions are applied to show that if G is a K4(7)-minor free graph, then χr(G) ≤ f(r) if and only if G is not isomorphic to K6.

Keywords: Coloring; (k, r)-coloring; r-hued list coloring; Graph minor; Decompositions (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300320301752
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:384:y:2020:i:c:s0096300320301752

DOI: 10.1016/j.amc.2020.125206

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().