Abstract
| Original language | English |
|---|---|
| Place of Publication | Enschede |
| Publisher | University of Twente, Department of Applied Mathematics |
| Publication status | Published - 2003 |
Publication series
| Name | Memorandum |
|---|---|
| Publisher | Department of Applied Mathematics, University of Twente |
| No. | 1706 |
| ISSN (Print) | 0169-2690 |
Fingerprint
Keywords
- MSC-05C85
- MSC-05C15
- IR-65891
- EWI-3526
- MSC-05C17
Cite this
}
Backbone colorings along perfect matchings. / Broersma, Haitze J.; Fujisawa, J.; Yoshimoto, K.
Enschede : University of Twente, Department of Applied Mathematics, 2003. (Memorandum; No. 1706).Research output: Book/Report › Report › Other research output
TY - BOOK
T1 - Backbone colorings along perfect matchings
AU - Broersma, Haitze J.
AU - Fujisawa, J.
AU - Yoshimoto, K.
PY - 2003
Y1 - 2003
N2 - 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.
AB - 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.
KW - MSC-05C85
KW - MSC-05C15
KW - IR-65891
KW - EWI-3526
KW - MSC-05C17
M3 - Report
T3 - Memorandum
BT - Backbone colorings along perfect matchings
PB - University of Twente, Department of Applied Mathematics
CY - Enschede
ER -