On acyclically 4-colorable maximal planar graphs

Enqiang Zhu, Zepeng Li, Zehui Shao and Jin Xu

Applied Mathematics and Computation, 2018, vol. 329, issue C, 402-407

Abstract: An acyclic coloring of a graph is a proper coloring of the graph, for which every cycle uses at least three colors. Let G4 be the set of maximal planar graphs of minimum degree 4, such that each graph in G4 contains exactly four odd-vertices and the subgraph induced by the four odd-vertices contains a quadrilateral. In this article, we show that every acyclic 4-coloring of a maximal planar graph with exact four odd-vertices is locally equitable with regard to its four odd-vertices. Moreover, we obtain a necessary and sufficient condition for a graph in G4 to be acyclically 4-colorable, and give an enumeration of the acyclically 4-colorable graphs in G4.

Keywords: Acyclically coloring; Maximal planar graphs; Locally equitable coloring; Necessary and sufficient condition; Enumeration (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300318301176
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:329:y:2018:i:c:p:402-407

DOI: 10.1016/j.amc.2018.02.015

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 ().