# Backbone colorings for networks: tree and path backbones

Haitze J. Broersma, F.V. Fomin, P.A. Golovach, Gerhard Woeginger

Research output: Book/ReportReportOther research output

## 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.
Original language Undefined Enschede University of Twente, Department of Applied Mathematics Published - 2003

### Publication series

Name Memorandum Department of Applied Mathematics, University of Twente 1705 0169-2690

• MSC-05C85
• MSC-05C15
• IR-65890
• EWI-3525
• MSC-05C17