查晓亚.Edge Partition of Graphs Embeddable in the Projective Plane and the Klein Bottle[J].数学研究及应用,2019,39(6):581~592
Edge Partition of Graphs Embeddable in the Projective Plane and the Klein Bottle
Edge Partition of Graphs Embeddable in the Projective Plane and the Klein Bottle
投稿时间:2019-09-22  修订日期:2019-10-10
DOI:10.3770/j.issn:2095-2651.2019.06.005
中文关键词:  surface  planar graph  edge partition  thickness  outerthickness  caterpillar tree  projective plane  Klein bottle
英文关键词:surface  planar graph  edge partition  thickness  outerthickness  caterpillar tree  projective plane  Klein bottle
基金项目:
作者单位
查晓亚 Department of Mathematical Sciences, Middle Tennessee State University, Murfreesboro, TN 37132, U. S. A. 
摘要点击次数: 40
全文下载次数: 66
中文摘要:
      In a previous paper by the author joint with Baogang XU published in Discrete Math in 2018, we show that every non-planar toroidal graph can be edge partitioned into a planar graph and an outerplanar graph. This edge partition then implies some results in thickness and outerthickness of toroidal graphs. In particular, if each planar graph has outerthickness at most $2$ (conjectured by Chartrand, Geller and Hedetniemi in 1971 and the confirmation of the conjecture was announced by Gon\c{c}alves in 2005), then the outerthickness of toroidal graphs is at most 3 which is the best possible due to $K_7$. In this paper we continue to study the edge partition for projective planar graphs and Klein bottle embeddable graphs. We show that (1) every non-planar but projective planar graph can be edge partitioned into a planar graph and a union of caterpillar trees; and (2) every non-planar Klein bottle embeddable graph can be edge partitioned into a planar graph and a subgraph of two vertex amalgamation of a caterpillar tree with a cycle with pendant edges. As consequences, the thinkness of projective planar graphs and Klein bottle embeddabe graphs are at most $2$, which are the best possible, and the outerthickness of these graphs are at most $3$.
英文摘要:
      In a previous paper by the author joint with Baogang XU published in Discrete Math in 2018, we show that every non-planar toroidal graph can be edge partitioned into a planar graph and an outerplanar graph. This edge partition then implies some results in thickness and outerthickness of toroidal graphs. In particular, if each planar graph has outerthickness at most $2$ (conjectured by Chartrand, Geller and Hedetniemi in 1971 and the confirmation of the conjecture was announced by Gon\c{c}alves in 2005), then the outerthickness of toroidal graphs is at most 3 which is the best possible due to $K_7$. In this paper we continue to study the edge partition for projective planar graphs and Klein bottle embeddable graphs. We show that (1) every non-planar but projective planar graph can be edge partitioned into a planar graph and a union of caterpillar trees; and (2) every non-planar Klein bottle embeddable graph can be edge partitioned into a planar graph and a subgraph of two vertex amalgamation of a caterpillar tree with a cycle with pendant edges. As consequences, the thinkness of projective planar graphs and Klein bottle embeddabe graphs are at most $2$, which are the best possible, and the outerthickness of these graphs are at most $3$.
查看全文  查看/发表评论  下载PDF阅读器