Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Backbone colorings for networks: tree and path backbones

Share/Save/Bookmark

Broersma, H.J. and Fomin, F.V. and Golovach, P.A. and Woeginger, G.J. (2003) Backbone colorings for networks: tree and path backbones. [Report]

[img]
Preview
PDF
245Kb
Abstract:
We introduce and study backbone colorings, a variation on classical vertex colorings: Given a graph $G=(V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a backbone coloring for $G$ and $H$ is a proper vertex coloring $V\rightarrow \{1,2,\ldots\}$ of $G$ in which the colors assigned to adjacent vertices in $H$ differ by at least two. We study the cases where the backbone is either a spanning tree or a spanning path.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65890
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page