Backbone colorings for graphs: Tree and path backbones

DOI10.1002/JGT.20228MaRDI QIDQ3445508zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Petr A. Golovach, Gerhard J. Woeginger, Hajo Broersma

Publication date 11 June 2007

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.20228

zbMATH Keywords

computational complexitygraph coloringgraph labelingplanar graphspanning pathspanning tree

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Eulerian and Hamiltonian graphs (05C45) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On backbone coloring of graphs
• Backbone colourings of graphs
• Backbone colouring: tree backbones with small diameter in planar graphs
• The \(\lambda\)-backbone colorings of graphs with tree backbones
• Backbone coloring for graphs with large girths
• Backbone coloring for triangle-free planar graphs
• The backbone coloring problem for bipartite backbones
• Backbone colorings of graphs with bounded degree
• Backbone colorings and generalized Mycielski graphs
• Backbone coloring of graphs with galaxy backbones

Cited in

(26)

• Labeling bipartite permutation graphs with a condition at distance two
• Circular backbone colorings: on matching and tree backbones of planar graphs
• Optimal backbone coloring of split graphs with matching backbones
• The computational complexity of the backbone coloring problem for planar graphs with connected backbones
• Backbone coloring of planar graphs for \(C_8\)-free or \(C_9\)-free
• Backbone coloring for triangle-free planar graphs
• List backbone colouring of graphs
• The \(\lambda\)-backbone colorings of graphs with tree backbones
• (Circular) backbone colouring: forest backbones in planar graphs
• Backbone colourings of graphs
• The computational complexity of -backbone colorings of graphs with n-complete backbones
• Backbone coloring for graphs with large girths
• Backbone colouring: tree backbones with small diameter in planar graphs
• On backbone coloring of graphs
• On list backbone coloring of graphs.
• The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
• The backbone coloring problem for bipartite backbones
• On the existence of tree backbones that realize the chromatic number on a backbone coloring
• Steinberg-like theorems for backbone colouring
• Backbone colorings for networks.
• Steinberg-like theorems for backbone colouring
• Backbone coloring of graphs with galaxy backbones
• Backbone coloring of graphs with galaxy backbones
• Backbone coloring of planar graphs without special circles
• On \(\lambda\)-backbone coloring of cliques with tree backbones in linear time
• Backbone colorings of graphs with bounded degree

This page was built for publication: Backbone colorings for graphs: Tree and path backbones

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