Complexity of conditional colorability of graphs

Xueliang Li, Xueliang Li, Xiangmei Yao, Wenli Zhou, Haitze J. Broersma

Research output: Contribution to journalArticleAcademicpeer-review

15 Citations (Scopus)

Abstract

For positive integers $k$ and $r$, a conditional $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex $v$ of degree $d(v)$ in $G$ is adjacent to vertices with at least $\min\{r,d(v)\}$ different colors. The smallest integer $k$ for which a graph $G$ has a conditional $(k,r)$-coloring is called the $r$th-order conditional chromatic number, and is denoted by $X_r(G)$. It is easy to see that conditional coloring is a generalization of traditional vertex coloring (the case $r=1$). In this work, we consider the complexity of the conditional colorability of graphs. Our main result is that conditional (3,2)-colorability remains NP-complete when restricted to planar bipartite graphs with maximum degree at most 3 and arbitrarily high girth. This differs considerably from the well-known result that traditional 3-colorability is polynomially solvable for graphs with maximum degree at most 3. On the other hand we show that (3,2)-colorability is polynomially solvable for graphs with bounded tree-width. We also prove that some other well-known complexity results for traditional coloring still hold for conditional coloring.
Original languageUndefined
Pages (from-to)320-324
Number of pages5
JournalApplied mathematics letters
Volume22
Issue number3
DOIs
Publication statusPublished - Mar 2009

Keywords

  • Conditional coloring
  • METIS-264415
  • NP-complete
  • (Conditional) chromatic number
  • Vertex coloring
  • Algorithm
  • Complexity
  • EWI-15829
  • IR-67841

Cite this

Li, Xueliang ; Li, Xueliang ; Yao, Xiangmei ; Zhou, Wenli ; Broersma, Haitze J. / Complexity of conditional colorability of graphs. In: Applied mathematics letters. 2009 ; Vol. 22, No. 3. pp. 320-324.
@article{02b21b5de0834fe6be7bf6e40b8b0a7f,
title = "Complexity of conditional colorability of graphs",
abstract = "For positive integers $k$ and $r$, a conditional $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex $v$ of degree $d(v)$ in $G$ is adjacent to vertices with at least $\min\{r,d(v)\}$ different colors. The smallest integer $k$ for which a graph $G$ has a conditional $(k,r)$-coloring is called the $r$th-order conditional chromatic number, and is denoted by $X_r(G)$. It is easy to see that conditional coloring is a generalization of traditional vertex coloring (the case $r=1$). In this work, we consider the complexity of the conditional colorability of graphs. Our main result is that conditional (3,2)-colorability remains NP-complete when restricted to planar bipartite graphs with maximum degree at most 3 and arbitrarily high girth. This differs considerably from the well-known result that traditional 3-colorability is polynomially solvable for graphs with maximum degree at most 3. On the other hand we show that (3,2)-colorability is polynomially solvable for graphs with bounded tree-width. We also prove that some other well-known complexity results for traditional coloring still hold for conditional coloring.",
keywords = "Conditional coloring, METIS-264415, NP-complete, (Conditional) chromatic number, Vertex coloring, Algorithm, Complexity, EWI-15829, IR-67841",
author = "Xueliang Li and Xueliang Li and Xiangmei Yao and Wenli Zhou and Broersma, {Haitze J.}",
note = "eemcs-eprint-15829",
year = "2009",
month = "3",
doi = "10.1016/j.aml.2008.04.003",
language = "Undefined",
volume = "22",
pages = "320--324",
journal = "Applied mathematics letters",
issn = "0893-9659",
publisher = "Elsevier",
number = "3",

}

Complexity of conditional colorability of graphs. / Li, Xueliang; Li, Xueliang; Yao, Xiangmei; Zhou, Wenli; Broersma, Haitze J.

In: Applied mathematics letters, Vol. 22, No. 3, 03.2009, p. 320-324.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Complexity of conditional colorability of graphs

AU - Li, Xueliang

AU - Li, Xueliang

AU - Yao, Xiangmei

AU - Zhou, Wenli

AU - Broersma, Haitze J.

N1 - eemcs-eprint-15829

PY - 2009/3

Y1 - 2009/3

N2 - For positive integers $k$ and $r$, a conditional $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex $v$ of degree $d(v)$ in $G$ is adjacent to vertices with at least $\min\{r,d(v)\}$ different colors. The smallest integer $k$ for which a graph $G$ has a conditional $(k,r)$-coloring is called the $r$th-order conditional chromatic number, and is denoted by $X_r(G)$. It is easy to see that conditional coloring is a generalization of traditional vertex coloring (the case $r=1$). In this work, we consider the complexity of the conditional colorability of graphs. Our main result is that conditional (3,2)-colorability remains NP-complete when restricted to planar bipartite graphs with maximum degree at most 3 and arbitrarily high girth. This differs considerably from the well-known result that traditional 3-colorability is polynomially solvable for graphs with maximum degree at most 3. On the other hand we show that (3,2)-colorability is polynomially solvable for graphs with bounded tree-width. We also prove that some other well-known complexity results for traditional coloring still hold for conditional coloring.

AB - For positive integers $k$ and $r$, a conditional $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex $v$ of degree $d(v)$ in $G$ is adjacent to vertices with at least $\min\{r,d(v)\}$ different colors. The smallest integer $k$ for which a graph $G$ has a conditional $(k,r)$-coloring is called the $r$th-order conditional chromatic number, and is denoted by $X_r(G)$. It is easy to see that conditional coloring is a generalization of traditional vertex coloring (the case $r=1$). In this work, we consider the complexity of the conditional colorability of graphs. Our main result is that conditional (3,2)-colorability remains NP-complete when restricted to planar bipartite graphs with maximum degree at most 3 and arbitrarily high girth. This differs considerably from the well-known result that traditional 3-colorability is polynomially solvable for graphs with maximum degree at most 3. On the other hand we show that (3,2)-colorability is polynomially solvable for graphs with bounded tree-width. We also prove that some other well-known complexity results for traditional coloring still hold for conditional coloring.

KW - Conditional coloring

KW - METIS-264415

KW - NP-complete

KW - (Conditional) chromatic number

KW - Vertex coloring

KW - Algorithm

KW - Complexity

KW - EWI-15829

KW - IR-67841

U2 - 10.1016/j.aml.2008.04.003

DO - 10.1016/j.aml.2008.04.003

M3 - Article

VL - 22

SP - 320

EP - 324

JO - Applied mathematics letters

JF - Applied mathematics letters

SN - 0893-9659

IS - 3

ER -