Backbone colouring: tree backbones with small diameter in planar graphs

DOI10.1016/J.TCS.2013.03.003MaRDI QIDQ387001zbMATH OpenOpenAlexFDO

Authors Victor Campos, Frédéric Havet, Rudini M. Sampaio, Ana Silva

Publication date 11 December 2013

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

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

zbMATH Keywords

planar graphsbackbone colouringBroersma's conjecture

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Backbone colourings of graphs
• Backbone coloring for triangle-free planar graphs
• Backbone coloring for \(C_4\)-free planar graphs
• Backbone coloring for \(C_5\)-free planar graphs
• Backbone coloring of planar graphs for \(C_8\)-free or \(C_9\)-free

Cites work

• Backbone coloring for \(C_4\)-free planar graphs
• Backbone coloring of planar graphs without special circles
• Backbone colorings for graphs: Tree and path backbones
• Backbone colorings for networks.
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• On backbone coloring of graphs
• \(\lambda \)-backbone colorings along pairwise disjoint stars and matchings

Cited in

(13)

• Backbone colorings for graphs: Tree and path backbones
• On the existence of tree backbones that realize the chromatic number on a backbone coloring
• Steinberg-like theorems for backbone colouring
• Steinberg-like theorems for backbone colouring
• Circular backbone colorings: on matching and tree backbones of planar graphs
• Backbone coloring of graphs with galaxy backbones
• Backbone colourings of graphs
• scientific article; zbMATH DE number 6178933 (Why is no real title available?)
• Backbone coloring for graphs with large girths
• Backbone colorings and generalized Mycielski graphs
• The computational complexity of the backbone coloring problem for planar graphs with connected backbones
• Backbone coloring for triangle-free planar graphs
• (Circular) backbone colouring: forest backbones in planar graphs

This page was built for publication: Backbone colouring: tree backbones with small diameter in planar graphs

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