Tree-colorable maximal planar graphs

MaRDI QIDQ6249964zbMATH OpenFDO

Authors Enqiang Zhu, Zepeng Li, Zehui Shao, Jin Xu

Publication date 19 March 2014

Abstract: A tree-coloring of a maximal planar graph is a proper vertex $4$-coloring such that every bichromatic subgraph, induced by this coloring, is a tree. A maximal planar graph $G$ is tree-colorable if $G$ has a tree-coloring. In this article, we prove that a tree-colorable maximal planar graph $G$ with $delta(G)geq4$ contains at least four odd-vertices. Moreover, for a tree-colorable maximal planar graph of minimum degree 4 that contains exactly four odd-vertices, we show that the subgraph induced by its four odd-vertices is not a claw and contains no triangles.

This page was built for publication: Tree-colorable maximal planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6249964)