(Circular) backbone colouring: forest backbones in planar graphs

DOI10.1016/J.DAM.2014.01.011MaRDI QIDQ2449063zbMATH OpenOpenAlexFDO

Authors Mathieu Liedloff, Ioan Todinca, Frédéric Havet, Andrew D. King

Publication date 6 May 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-00957243/file/complexity-backbone.pdf

zbMATH Keywords

backbone colouringNP-completeplanar graphtree backbone

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• 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

Cites work

• -backbone colorings along pairwise disjoint stars and matchings
• Backbone colorings for graphs: Tree and path backbones
• Backbone colorings for networks.
• Backbone colouring: tree backbones with small diameter in planar graphs
• Decomposing a planar graph of girth 5 into an independent set and a forest
• scientific article; zbMATH DE number 434910 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1882351 (Why is no real title available?)
• On the complexity of H-colouring planar graphs
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• The complexity of satisfiability problems

Cited in

(10)

• Circular backbone colorings: on matching and tree backbones of planar graphs
• The computational complexity of the backbone coloring problem for planar graphs with connected backbones
• The backbone coloring of planar graphs without 7-cycles
• On the existence of tree backbones that realize the chromatic number on a backbone coloring
• List circular backbone colouring
• Steinberg-like theorems for backbone colouring
• Steinberg-like theorems for backbone colouring
• Backbone coloring of graphs with galaxy backbones
• Backbone coloring of graphs with galaxy backbones
• On \(\lambda\)-backbone coloring of cliques with tree backbones in linear time

This page was built for publication: (Circular) backbone colouring: forest backbones in planar graphs

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