Backbone colorings along perfect matchings

Haitze J. Broersma, J. Fujisawa, K. Yoshimoto

Research output: Book/ReportReportOther research output

21 Downloads (Pure)


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. In a recent paper, backbone colorings were introduced and studied in cases were the backbone is either a spanning tree or a spanning path. Here we study the case where the backbone is a perfect matching. We show that for perfect matching backbones of $G$ the number of colors needed for a backbone coloring of $G$ can roughly differ by a multiplicative factor of at most $\frac{4}{3}$ from the chromatic number $\chi(G)$. We show that the computational complexity of the problem ``Given a graph $G$ with a perfect matching $M$, and an integer $\ell$, is there a backbone coloring for $G$ and $M$ with at most $\ell$ colors?'' jumps from polynomial to NP-complete between $\ell=3$ and $\ell=4$. Finally, we consider the case where $G$ is a planar graph.
Original languageEnglish
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-65891
  • EWI-3526
  • MSC-05C17


Dive into the research topics of 'Backbone colorings along perfect matchings'. Together they form a unique fingerprint.

Cite this