Backbone colorings for graphs: Tree and path backbones
From MaRDI portal
Publication:3445508
DOI10.1002/jgt.20228zbMath1118.05031WikidataQ60488754 ScholiaQ60488754MaRDI QIDQ3445508
Fedor V. Fomin, Gerhard J. Woeginger, Petr A. Golovach, Hajo J. 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
computational complexity; graph coloring; spanning tree; planar graph; spanning path; graph labeling
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
05C78: Graph labelling (graceful graphs, bandwidth, etc.)
05C45: Eulerian and Hamiltonian graphs
Related Items
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, Backbone coloring of graphs with galaxy backbones, Backbone coloring of graphs with galaxy backbones, Backbone coloring for graphs with large girths, Backbone colouring: tree backbones with small diameter in planar graphs, On 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, Backbone coloring of planar graphs without special circles, Backbone colorings of graphs with bounded degree, 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, 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, (Circular) backbone colouring: forest backbones in planar graphs, Backbone colourings of graphs
Cites Work
