𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of the T-coloring problem for graphs with small degree

✍ Scribed by Krzysztof Giaro; Robert Janczewski; Michał Małafiejski

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
194 KB
Volume
129
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

In the paper we consider a generalized vertex coloring model, namely T -coloring. For a given ÿnite set T of nonnegative integers including 0, a proper vertex coloring is called a T -coloring if the distance of the colors of adjacent vertices is not an element of T . This problem is a generalization of the classic vertex coloring and appeared as a model of the frequency assignment problem. We present new results concerning the complexity of T -coloring with the smallest span on graphs with small degree . We distinguish between the cases that appear to be polynomial or NP-complete. More speciÿcally, we show that our problem is polynomial on graphs with 6 2 and in the case of k-regular graphs it becomes NP-hard even for every ÿxed T and every k ¿ 3. Also, the case of graphs with = 3 is under consideration. Our results are based on the complexity properties of the homomorphism of graphs.

📜 SIMILAR VOLUMES

An upper bound on the number of edges of
An upper bound on the number of edges of edge-coloring critical graphs with high maximum degree
✍ Lian-ying Miao; Shi-you Pang; Jian-liang Wu 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 100 KB

In this paper, we prove that any edge-coloring critical graph G with maximum degree ¿ (11 + √ 49 -24 )=2, where 6 1, has the size at least 3(|V (G)| -) + 1 if 6 7 or if ¿ 8 and |V (G)| ¿ 2 --4 -( + 6)=( -6), where is the minimum degree of G. It generalizes a result of Sanders and Zhao.

The complexity of the matching-cut probl
The complexity of the matching-cut problem for planar graphs and other graph classes
✍ Paul Bonsma 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB

## Abstract The Matching‐Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be ${\cal{NP}}$‐complete when restricted to graphs with maximum deg

A note on the complexity of longest path
A note on the complexity of longest path problems related to graph coloring
✍ P.M. Pardalos; A. Migdalas 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 194 KB

In this note, we show that some problems related to the length of the longest simple path from a given vertex in a graph are NP-complete. We also discuss an extension to the graph coloring problem.