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

作者：

Highlights：

• A refined concept of K_4(h)-minor free is introduced to extend the class of serial-parallel graphs.

• Decomposition theorems for K_4(h)-minor free graphs are obtained for smaller values of h, such as h = 5,6,7.

• Utilizing the decompositions of K_4(h)-minor free graphs, a former conjecture on r-hued colorings of planar graphs have been validated for K_4(h)-minor free graphs when h is at most 7.

摘要

•A refined concept of K_4(h)-minor free is introduced to extend the class of serial-parallel graphs.•Decomposition theorems for K_4(h)-minor free graphs are obtained for smaller values of h, such as h = 5,6,7.•Utilizing the decompositions of K_4(h)-minor free graphs, a former conjecture on r-hued colorings of planar graphs have been validated for K_4(h)-minor free graphs when h is at most 7.

论文关键词：Coloring,(k, r)-coloring,r-hued list coloring,Graph minor,Decompositions

论文评审过程：Received 23 March 2019, Revised 25 February 2020, Accepted 7 March 2020, Available online 30 May 2020, Version of Record 30 May 2020.

论文官网地址：https://doi.org/10.1016/j.amc.2020.125206