On backbone coloring of graphs

DOI10.1007/S10878-010-9342-6MaRDI QIDQ434190zbMATH OpenOpenAlexFDO

Authors Yuehua Bu, Weifan Wang, Mickaël Montassier, André Raspaud

Publication date 10 July 2012

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-010-9342-6

zbMATH Keywords

backbone coloringHalin graphHamiltonian pathmaximum average degreespanning tree

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Backbone colourings of graphs
• On list backbone coloring of graphs.
• Backbone coloring for C₅-free planar graphs
• Backbone colorings for graphs: Tree and path backbones
• Backbone colorings of graphs with bounded degree

Cites work

• (d,1)-total labeling of graphs with a given maximum average degree
• -backbone colorings along pairwise disjoint stars and matchings
• A bound on the chromatic number of the square of a planar graph
• Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
• Backbone colorings and generalized Mycielski graphs
• Backbone colorings for graphs: Tree and path backbones
• Backbone colorings of graphs with bounded degree
• Every planar map is four colorable
• Labeling Chordal Graphs: Distance Two Condition
• Labeling Planar Graphs with Conditions on Girth and Distance Two
• Labeling products of complete graphs with a condition at distance two
• Labelling Graphs with a Condition at Distance 2
• Lengths of cycles in halin graphs
• List coloring Halin graphs.
• Minimum cycle bases of Halin graphs
• The $L(2,1)$-Labeling Problem on Graphs
• The 2-dipath chromatic number of Halin graphs
• The L(2,1)-labelling of trees
• The vertex-face total chromatic number of Halin graphs

Cited in

(26)

• -backbone colorings along pairwise disjoint stars and matchings
• On the role of 3s for the 1-2-3 conjecture
• 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
• Backbone colourings of graphs
• On the role of 3's for the 1-2-3 conjecture
• scientific article; zbMATH DE number 5004842 (Why is no real title available?)
• Backbone colorings for graphs: Tree and path backbones
• A theoretical analysis of backtracking in the graph coloring problem
• Backbone coloring for graphs with large girths
• Backbone colouring: tree backbones with small diameter in planar graphs
• List backbone coloring of paths and cycles
• On list backbone coloring of graphs.
• scientific article; zbMATH DE number 6178933 (Why is no real title available?)
• The backbone coloring problem for bipartite backbones
• On the existence of tree backbones that realize the chromatic number on a backbone coloring
• Backbone coloring for C₄-free planar graphs
• Steinberg-like theorems for backbone colouring
• Backbone colorings for networks.
• Backbone coloring of graphs with galaxy backbones
• Backbone coloring of planar graphs without special circles
• Backbone colorings of graphs with bounded degree

This page was built for publication: On backbone coloring of graphs

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