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

15 Downloads (Pure)


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 languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 2003

Publication series

PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)0169-2690


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

Cite this