Backbone coloring of planar graphs without special circles

DOI10.1016/J.TCS.2011.06.032MaRDI QIDQ650874zbMATH OpenOpenAlexFDO

Authors Yuehua Bu, Yulin Li

Publication date 7 December 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.06.032

zbMATH Keywords

backbone coloringplanar graphspanning tree

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.

Recommendations

• scientific article; zbMATH DE number 6178933
• The backbone coloring of planar graphs without 7-cycles
• Backbone coloring of planar graphs for \(C_8\)-free or \(C_9\)-free
• Backbone coloring for C₄-free planar graphs
• Backbone coloring for C₅-free planar graphs

Cites work

• -backbone colorings along pairwise disjoint stars and matchings
• Backbone coloring for C₄-free planar graphs
• Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
• Backbone colorings for graphs: Tree and path backbones
• Backbone colorings for networks.
• Graph theory
• On backbone coloring of graphs

Cited in

(10)

• Circular backbone colorings: on matching and tree backbones of planar graphs
• Backbone coloring of planar graphs for \(C_8\)-free or \(C_9\)-free
• Backbone coloring for triangle-free planar graphs
• Backbone colourings of graphs
• Backbone coloring for C₅-free planar graphs
• The backbone coloring of planar graphs without 7-cycles
• Backbone colouring: tree backbones with small diameter in planar graphs
• scientific article; zbMATH DE number 6178933 (Why is no real title available?)
• On the existence of tree backbones that realize the chromatic number on a backbone coloring
• Backbone coloring for C₄-free planar graphs

This page was built for publication: Backbone coloring of planar graphs without special circles

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