Backbone colorings along perfect matchings

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

Research output: Book/ReportReportOther research output

7 Downloads (Pure)

Abstract

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

NameMemorandum
PublisherDepartment of Applied Mathematics, University of Twente
No.1706
ISSN (Print)0169-2690

Fingerprint

Perfect Matching
Backbone
Colouring
Spanning Subgraph
Vertex Coloring
Graph in graph theory
Chromatic number
Spanning tree
Planar graph
Multiplicative
Computational Complexity
Jump
Adjacent
NP-complete problem
Path
Polynomial
Integer
Color

Keywords

  • MSC-05C85
  • MSC-05C15
  • IR-65891
  • EWI-3526
  • MSC-05C17

Cite this

Broersma, H. J., Fujisawa, J., & Yoshimoto, K. (2003). Backbone colorings along perfect matchings. (Memorandum; No. 1706). Enschede: University of Twente, Department of Applied Mathematics.
Broersma, Haitze J. ; Fujisawa, J. ; Yoshimoto, K. / Backbone colorings along perfect matchings. Enschede : University of Twente, Department of Applied Mathematics, 2003. (Memorandum; 1706).
@book{76ad6a22f28d45379f60dba3ae8ce037,
title = "Backbone colorings along perfect matchings",
abstract = "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.",
keywords = "MSC-05C85, MSC-05C15, IR-65891, EWI-3526, MSC-05C17",
author = "Broersma, {Haitze J.} and J. Fujisawa and K. Yoshimoto",
year = "2003",
language = "English",
series = "Memorandum",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1706",

}

Broersma, HJ, Fujisawa, J & Yoshimoto, K 2003, Backbone colorings along perfect matchings. Memorandum, no. 1706, University of Twente, Department of Applied Mathematics, Enschede.

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/ReportReportOther 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 -

Broersma HJ, Fujisawa J, Yoshimoto K. Backbone colorings along perfect matchings. Enschede: University of Twente, Department of Applied Mathematics, 2003. (Memorandum; 1706).