Bulletin of the
Korean Mathematical Society
BKMS

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016

Article

HOME ALL ARTICLES View

Bull. Korean Math. Soc. 2018; 55(2): 415-430

Online first article January 8, 2018      Printed March 30, 2018

https://doi.org/10.4134/BKMS.b170053

Copyright © The Korean Mathematical Society.

A sufficient condition for acyclic 5-choosability of planar graphs without 5-cycles

Lin Sun

Chongqing University of Arts and Sciences

Abstract

A proper vertex coloring of a graph $G$ is acyclic if $G$ contains no bicolored cycle. A graph $G$ is acyclically $L$-list colorable if for a given list assignment $L=\{L(v): v\in V(G)\}$, there exists an acyclic coloring $\phi$ of $G$ such that $\phi(v)\in L(v)$ for all $v\in V(G)$. A graph $G$ is acyclically $k$-choosable if $G$ is acyclically $L$-list colorable for any list assignment with $L(v)\geq k$ for all $v\in V(G)$. Let $G$ be a planar graph without $5$-cycles and adjacent $4$-cycles. In this article, we prove that $G$ is acyclically $5$-choosable if every vertex $v$ in $G$ is incident with at most one $i$-cycle, $i\in\{6,7\}$.

Keywords: planar graph, acyclic coloring, choosable, adjacent cycles, minimal counterexample

MSC numbers: 05C15