On backbone coloring of graphs

DOI10.1007/s10878-010-9342-6zbMath1245.90138OpenAlexW1995827095MaRDI QIDQ434190

Yuehua Bu, Mickaël Montassier, Wei Fan Wang, Andre 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

spanning treeHamiltonian pathHalin graphmaximum average degreebackbone coloring

Mathematics Subject Classification ID

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

Related Items (7)

Backbone coloring for triangle-free planar graphs ⋮ Backbone colouring: tree backbones with small diameter in planar graphs ⋮ On the role of 3's for the 1-2-3 conjecture ⋮ Backbone coloring of planar graphs without special circles ⋮ On the role of 3s for the 1--2--3 conjecture ⋮ On the Existence of Tree Backbones that Realize the Chromatic Number on a Backbone Coloring ⋮ Backbone coloring of planar graphs for \(C_8\)-free or \(C_9\)-free

Cites Work

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

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