Back to Search Start Over

Tree-colorable maximal planar graphs

Authors :
Zhu, Enqiang
Li, Zepeng
Shao, Zehui
Xu, Jin
Publication Year :
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)\geq 4$ 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.<br />Comment: 18pages,10figures

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1403.5013
Document Type :
Working Paper