TY - JOUR

T1 - Injective Colorings with Arithmetic Constraints

AU - Astromujoff, N.

AU - Chapelle, M.

AU - Matamala, M.

AU - Todinca, I.

AU - Zamora, J.

N1 - Publisher Copyright:
© 2015, Springer Japan.
Copyright:
Copyright 2015 Elsevier B.V., All rights reserved.

PY - 2015/11/1

Y1 - 2015/11/1

N2 - An injective coloring of a graph is a vertex labeling such that two vertices sharing a common neighbor get different labels. In this work we introduce and study what we call additive colorings. An injective coloring c:V(G)→Z of a graph G is an additive coloring if for every uv,vw in E(G), c(u)+c(w)≠2c(v). The smallest integer k such that an injective (resp. additive) coloring of a given graph G exists with k colors (resp. colors in {1,…,k}) is called the injective (resp. additive) chromatic number (resp. index). They are denoted by χi(G) and χa′(G), respectively. In the first part of this work, we present several upper bounds for the additive chromatic index. On the one hand, we prove a super linear upper bound in terms of the injective chromatic number for arbitrary graphs, as well as a linear upper bound for bipartite graphs and trees. Complete graphs are extremal graphs for the super linear bound, while complete balanced bipartite graphs are extremal graphs for the linear bound. On the other hand, we prove a quadratic upper bound in terms of the maximum degree. In the second part, we study the computational complexity of computing χa′(G). We prove that it can be computed in polynomial time for trees. We also prove that for bounded treewidth graphs, to decide whether χa′(G)≤k, for a fixed k, can be done in polynomial time. On the other hand, we show that for cubic graphs it is NP-complete to decide whether χa′(G)≤4. We also prove that for every ϵ>0 there is a polynomial time approximation algorithm with approximation factor n1/3+ϵ for χa′(G), when restricted to split graphs. However, unless P=NP, for every ϵ>0 there is no polynomial time approximation algorithm with approximation factor n1/3-ϵ for χa′(G), even when restricted to split graphs.

AB - An injective coloring of a graph is a vertex labeling such that two vertices sharing a common neighbor get different labels. In this work we introduce and study what we call additive colorings. An injective coloring c:V(G)→Z of a graph G is an additive coloring if for every uv,vw in E(G), c(u)+c(w)≠2c(v). The smallest integer k such that an injective (resp. additive) coloring of a given graph G exists with k colors (resp. colors in {1,…,k}) is called the injective (resp. additive) chromatic number (resp. index). They are denoted by χi(G) and χa′(G), respectively. In the first part of this work, we present several upper bounds for the additive chromatic index. On the one hand, we prove a super linear upper bound in terms of the injective chromatic number for arbitrary graphs, as well as a linear upper bound for bipartite graphs and trees. Complete graphs are extremal graphs for the super linear bound, while complete balanced bipartite graphs are extremal graphs for the linear bound. On the other hand, we prove a quadratic upper bound in terms of the maximum degree. In the second part, we study the computational complexity of computing χa′(G). We prove that it can be computed in polynomial time for trees. We also prove that for bounded treewidth graphs, to decide whether χa′(G)≤k, for a fixed k, can be done in polynomial time. On the other hand, we show that for cubic graphs it is NP-complete to decide whether χa′(G)≤4. We also prove that for every ϵ>0 there is a polynomial time approximation algorithm with approximation factor n1/3+ϵ for χa′(G), when restricted to split graphs. However, unless P=NP, for every ϵ>0 there is no polynomial time approximation algorithm with approximation factor n1/3-ϵ for χa′(G), even when restricted to split graphs.

KW - Dynamic programming

KW - Injective colorings

KW - NP-completeness

KW - Polynomial time algorithms

UR - http://www.scopus.com/inward/record.url?scp=84945918429&partnerID=8YFLogxK

U2 - 10.1007/s00373-014-1520-3

DO - 10.1007/s00373-014-1520-3

M3 - Article

AN - SCOPUS:84945918429

VL - 31

SP - 2003

EP - 2017

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

SN - 0911-0119

IS - 6

ER -