# zbMATH — the first resource for mathematics

Complexity of the improper twin edge coloring of graphs. (English) Zbl 1371.05067
Summary: Let $$G$$ be a graph whose each component has order at least 3. Let $$s : E(G) \rightarrow \mathbb {Z}_k$$ for some integer $$k\geq 2$$ be an improper edge coloring of $$G$$ (where adjacent edges may be assigned the same color). If the induced vertex coloring $$c : V (G) \rightarrow \mathbb {Z}_k$$ defined by $$c(v) = \sum_{e\in E_v} s(e)$$ in $$\mathbb {Z}_k$$, (where the indicated sum is computed in $$\mathbb {Z}_k$$ and $$E_v$$ denotes the set of all edges incident to $$v$$) results in a proper vertex coloring of $$G$$, then we refer to such a coloring as an improper twin $$k$$-edge coloring. The minimum $$k$$ for which $$G$$ has an improper twin $$k$$-edge coloring is called the improper twin chromatic index of $$G$$ and is denoted by $$\chi^\prime_{it}(G)$$. It is known that $$\chi^\prime_{it}(G)=\chi (G)$$, unless $$\chi (G) \equiv 2 \pmod 4$$ and in this case $$\chi^\prime_{it}(G)\in \{\chi (G), \chi (G)+1\}$$. In this paper, we first give a short proof of this result and we show that if $$G$$ admits an improper twin $$k$$-edge coloring for some positive integer $$k$$, then $$G$$ admits an improper twin $$t$$-edge coloring for all $$t\geq k$$; we call this the monotonicity property. In addition, we provide a linear time algorithm to construct an improper twin edge coloring using at most $$k+1$$ colors, whenever a $$k$$-vertex coloring is given. Then we investigate, to the best of our knowledge the first time in literature, the complexity of deciding whether $$\chi^\prime_{it}(G)=\chi (G)$$ or $$\chi^\prime_{it}(G)=\chi (G)+1$$, and we show that, just like in case of the edge chromatic index, it is NP-hard even in some restricted cases. Lastly, we exhibit several classes of graphs for which the problem is polynomial.
Reviewer: Reviewer (Berlin)
##### MSC:
 05C15 Coloring of graphs and hypergraphs 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text:
##### References:
  Addario-Berry, L; Aldred, REL; Dalal, K; Reed, BA, Vertex colouring edge partitions, J. Comb. Theory (B), 94, 237-244, (2005) · Zbl 1074.05031  Andrews, E; Helenius, L; Johnston, D; VerWys, J; Zhang, Ping, On twin edge colorings of graphs, Discuss. Math. Graph Theory, 34, 613-627, (2014) · Zbl 1305.05068  Anholcer, M; Cichacz, S, Group sum chromatic number of graphs, Eur. J. Comb., 55, 73-81, (2016) · Zbl 1333.05100  Anholcer, M., Cichacz, S., Milanic̆, M.: Group irregularity strength of connected graphs. J. Comb. Optim. 30(1), 1-17 (2015) · Zbl 1316.05078  Appel, K; Haken, W, The solution of the four-color map problem, Sci. Amer., 237, 108-121, (1977)  Brooks, RL, On colouring the nodes of a network, Math. Proc. Camb. Philos. Soc., 37, 194-197, (1941) · Zbl 0027.26403  Chartrand, G., Zhang, P.: Chromatic Graph Theory. CRC Press, Boca Raton (2008) · Zbl 1169.05001  Clarke, G., Demange, M., Roshchina, V.: Lecture Notes-Discrete Mathematics, RMIT University  Edwards, K; Hornák, M; Wozniak, M, On the neighbour-distinguishing index of a graph, Graphs Comb., 22, 341-350, (2006) · Zbl 1107.05032  Flandrin, E; Marczyk, A; Przybyło, J; Saclé, J-F; Woźniak, M, Neighbor sum distinguishing index, Graphs Comb., 29, 1329-1336, (2013) · Zbl 1272.05047  Garey, M.R., Johnson, D.S.: Computers and Intractability, a Guide to the Theory of $$\cal{NP}$$-Completeness. Freeman, New York (1979) · Zbl 0411.68039  Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics. Academic Press, New York (1980) · Zbl 0541.05054  Jones, R; Kolasinski, K; Okamoto, F; Zhang, P, Modular neighbor-distinguishing edge colorings of graphs, J. Combin. Math. Combin. Comput., 76, 159-175, (2011) · Zbl 1233.05104  Jones, R; Kolasinski, K; Okamoto, F; Zhang, P, On modular chromatic indexes of graphs, J. Combin. Math. Combin. Comput., 82, 295-306, (2012) · Zbl 1251.05057  Karonski, M; Luczak, T; Thomason, A, Edge weights and vertex colours, J. Combin. Theory (B), 91, 151-157, (2004) · Zbl 1042.05045  Kratsch, D; Stewart, L, Domination on cocomparability graphs, SIAM J. Discret. Math., 6, 400-417, (1993) · Zbl 0780.05032  Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: Efficiently four-coloring planar graphs. In: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 571-575, ACM (1996) · Zbl 0917.05030  Seamone, B.: The 1-2-3 Conjecture and related problems: a survey. arXiv:1211.5122 [math.CO] (2012) (Preprint)  Zhang, P.: Color-Induced Graph Colorings. Springer, Berlin (2015) · Zbl 1365.05006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.