Backbone colorings of graphs with bounded degree

DOI10.1016/J.DAM.2009.11.015MaRDI QIDQ968172zbMATH OpenOpenAlexFDO

Authors Jozef Miškuf, Riste Škrekovski, Martin Tancer

Publication date 5 May 2010

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

Full work available at URL https://doi.org/10.1016/j.dam.2009.11.015

zbMATH Keywords

coloringchannel assignmentcoloring numberbackbone coloringdistant labelings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• On backbone coloring of graphs
• Backbone colourings of graphs
• Backbone coloring for graphs with large girths
• The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
• Backbone colorings and generalized Mycielski graphs
• The backbone coloring problem for bipartite backbones
• Backbone colorings for graphs: Tree and path backbones
• Backbone coloring for triangle-free planar graphs
• Backbone coloring of graphs with galaxy backbones
• Backbone coloring of graphs with galaxy backbones

Cites work

• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• A characterisation of some 2-connected graphs and a comment on an algorithmic proof of Brooks' theorem
• 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
• Concentration of measure and isoperimetric inequalities in product spaces
• Graph colouring and the probabilistic method
• The computational complexity of \(\lambda\)-backbone colorings of graphs with \(n\)-complete backbones
• \(\lambda \)-backbone colorings along pairwise disjoint stars and matchings

Cited in

(20)

• Backbone colorings for graphs: Tree and path backbones
• 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 for \(C_8\)-free or \(C_9\)-free
• Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
• Backbone colourings of graphs
• The backbone coloring problem for bipartite backbones
• scientific article; zbMATH DE number 6178933 (Why is no real title available?)
• Backbone coloring for graphs with large girths
• On \(\lambda\)-backbone coloring of cliques with tree backbones in linear time
• The computational complexity of the backbone coloring problem for planar graphs with connected backbones
• Backbone colorings for networks.
• List backbone coloring of paths and cycles
• Improved Upper Bounds for λ-Backbone Colorings Along Matchings and Stars
• List backbone colouring of graphs
• Backbone coloring for triangle-free planar graphs
• On backbone coloring of graphs
• The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
• Optimal backbone coloring of split graphs with matching backbones

This page was built for publication: Backbone colorings of graphs with bounded degree

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