Backbone Coloring for Triangle-free Planar Graphs

发布时间：2022-01-02 06:42

　　Let G be a graph and H a subgraph of G. A backbone-k-coloring of（G, H） is a mapping f :V（G） → {1, 2, ···, k} such that |f（u）-f（v）| ≥ 2 if uv ∈ E（H） and |f（u）-f（v）| ≥ 1 if uv ∈ E（G）\E（H）.The backbone chromatic number of（G, H） denoted by χb（G, H） is the smallest integer k such that（G, H） has a backbone-k-coloring. In this paper, we prove that if G is either a connected triangle-free planar graph or a connected graph with mad（G） < 3, then there exists a spanning tree T of G such that χb（G, T） ≤ ... 

【文章来源】：Acta Mathematicae Applicatae Sinica. 2017,33(03)SCICSCD

【文章页数】：6 页

【文章目录】：
1 Introduction
2 Triangle-free Planar Graphs
3 Graphs with mad (G) <3



本文编号：3563681