Backbone coloring of planar graphs without special circles
type: Item
instance of: scholarly article
title: Backbone coloring of planar graphs without special circles
zbMATH Open document ID: 1230.05126
author: Yuehua Bu
author: Yulin Li
published in: Theoretical Computer Science
publication date: 2011-12-07T00:00:00Z
review text: Given a graph \(G = (V,E)\) and a spanning subgraph \(H\) of \(G\) (the backbone of \(G\)), a backbone \(k\)-coloring of \((G,H)\) is a proper vertex coloring \(f: V \rightarrow \{1, 2, \ldots, k\}\) of \(G\) such that \(|f(u) - f(v)| \geq 2\) if \(uv \in E(H)\) and \(|f(u) - f(v)| \geq 1\) if \(uv \in E(G)\setminus E(H)\). The authors prove that any connected planar graph \(G\) without adjacent triangles and without chordless \(6\)-cycles or chordless \(7\)-cycles admits a spanning tree \(T\) such that \((G,T)\) has a backbone \(4\)-coloring. A related result [\textit{W. Wang, Y. Bu, M. Montassier} and \textit{A. Raspaud}, ``On backbone coloring of graphs,'' J. Comb. Optim. 23, 79--93 (2012)] is as follows: Any connected non-bipartite planar graph \(G\) without cycles of length less than \(10\) admits a spanning tree \(T\) such that \((G,T)\) has a backbone \(4\)-coloring.
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5986980
zbMATH Keywords: backbone coloring
zbMATH Keywords: planar graph
zbMATH Keywords: spanning tree
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.06.032
OpenAlex ID: W2028290377
cites work: Q5422499
cites work: Backbone colorings for graphs: Tree and path backbones
cites work: \(\lambda \)-backbone colorings along pairwise disjoint stars and matchings
cites work: Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
cites work: Graph-Theoretic Concepts in Computer Science
cites work: On backbone coloring of graphs
cites work: 没有4- 圈的平面图的BB- 染色
DOI: 10.1016/J.TCS.2011.06.032
description: scientific article; zbMATH DE number 5986980