×

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.

MSC:

05C15 Coloring of graphs and hypergraphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

References:

[1] Addario-Berry, L., Aldred, R.E.L., Dalal, K., Reed, B.A.: Vertex colouring edge partitions. J. Comb. Theory (B) 94, 237-244 (2005) · Zbl 1074.05031 · doi:10.1016/j.jctb.2005.01.001
[2] 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 · doi:10.7151/dmgt.1756
[3] Anholcer, M., Cichacz, S.: Group sum chromatic number of graphs. Eur. J. Comb. 55, 73-81 (2016) · Zbl 1333.05100 · doi:10.1016/j.ejc.2016.02.002
[4] Anholcer, M., Cichacz, S., Milanic̆, M.: Group irregularity strength of connected graphs. J. Comb. Optim. 30(1), 1-17 (2015) · Zbl 1316.05078
[5] Appel, K., Haken, W.: The solution of the four-color map problem. Sci. Amer. 237, 108-121 (1977) · doi:10.1038/scientificamerican1077-108
[6] Brooks, R.L.: On colouring the nodes of a network. Math. Proc. Camb. Philos. Soc. 37, 194-197 (1941) · Zbl 0027.26403 · doi:10.1017/S030500410002168X
[7] Chartrand, G., Zhang, P.: Chromatic Graph Theory. CRC Press, Boca Raton (2008) · Zbl 1169.05001 · doi:10.1201/9781584888017
[8] Clarke, G., Demange, M., Roshchina, V.: Lecture Notes-Discrete Mathematics, RMIT University
[9] Edwards, K., Hornák, M., Wozniak, M.: On the neighbour-distinguishing index of a graph. Graphs Comb. 22, 341-350 (2006) · Zbl 1107.05032 · doi:10.1007/s00373-006-0671-2
[10] 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 · doi:10.1007/s00373-012-1191-x
[11] Garey, M.R., Johnson, D.S.: Computers and Intractability, a Guide to the Theory of \[\cal{NP}\] NP-Completeness. Freeman, New York (1979) · Zbl 0411.68039
[12] Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics. Academic Press, New York (1980) · Zbl 0541.05054
[13] 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
[14] 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
[15] Karonski, M., Luczak, T., Thomason, A.: Edge weights and vertex colours. J. Combin. Theory (B) 91, 151-157 (2004) · Zbl 1042.05045 · doi:10.1016/j.jctb.2003.12.001
[16] Kratsch, D., Stewart, L.: Domination on cocomparability graphs. SIAM J. Discret. Math. 6, 400-417 (1993) · Zbl 0780.05032 · doi:10.1137/0406032
[17] 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
[18] Seamone, B.: The 1-2-3 Conjecture and related problems: a survey. arXiv:1211.5122 [math.CO] (2012) (Preprint)
[19] Zhang, P.: Color-Induced Graph Colorings. Springer, Berlin (2015) · Zbl 1365.05006 · doi:10.1007/978-3-319-20394-2
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.