logo_acta

Acta Mathematica Vietnamica

On Chromatic Numbers of Two Extensions of Planar Graphs

icon-email Khosro Tajbakhsh

Abstract

In this paper, the acyclic chromatic and the circular list chromatic numbers of a simple $H$-minor free graph $G$ is considered, where $H \in\{K_5,K_{3,3}\}$. It is proved that the acyclic chromatic number (resp. the circular list chromatic number) of a simple $H$-minor free graph $G$ where $H \in \{K_5,K_{3,3}\}$ is at most 5 (resp. at most 8) and we conclude that $G$ is star 20-colorable. These results generalize the same known results on planar graphs. Moreover, some upper bounds for the coloring numbers of $H$-minor free graphs for $H\in \{K_5,K_{3,3},K_{r,s}\}$ and $r \leq 2$ are obtained. These results generalize some known results and give some new results on group choice number, group chromatic number, and the choice number of the mentioned graphs with much shorter proofs.