×

On the neighbor sum distinguishing index of planar graphs. (English) Zbl 1367.05066

Summary: Let \(c\) be a proper edge coloring of a graph \(G=(V,E)\) with integers \(1,2,\ldots,k\). Then \(k\geq \Delta(G)\), while Vizing’s theorem guarantees that we can take \(k\leq \Delta(G)+1\). On the course of investigating irregularities in graphs, it has been conjectured that with only slightly larger \(k\), that is, \(k=\Delta (G)+2\), we could enforce an additional strong feature of \(c\), namely that it attributes distinct sums of incident colors to adjacent vertices in \(G\) if only this graph has no isolated edges and is not isomorphic to \(C_5\). We prove the conjecture is valid for planar graphs of sufficiently large maximum degree. In fact an even stronger statement holds, as the necessary number of colors stemming from the result of Vizing is proved to be sufficient for this family of graphs. Specifically, our main result states that every planar graph \(G\) of maximum degree at least \(28\), which contains no isolated edges admits a proper edge coloring \(c:E\to \{1,2,\ldots ,\Delta(G)+1\}\) such that \(\sum_{e\ni u}c(e)\neq \sum_{e\ni v}c(e)\) for every edge \(uv\) of \(G\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C07 Vertex degrees

References:

[1] L.Addario‐Berry, K.Dalal, C.McDiarmid, B. A.Reed, and A.Thomason, Vertex‐colouring edge‐weightings, Combinatorica27(1) (2007), 1-12. · Zbl 1127.05034
[2] L.Addario‐Berry, K.Dalal, and B. A.Reed, Degree constrained subgraphs, Discrete Appl Math156(7) (2008), 1168-1174. · Zbl 1147.05055
[3] M.Aigner and E.Triesch, Irregular assignments of trees and forests, SIAM J Discrete Math3 (1990), 439-449. · Zbl 0735.05049
[4] S.Akbari, H.Bidkhori, and N.Nosrati, r‐Strong edge colorings of graphs, Discrete Math306 (2006), 3005-3010. · Zbl 1112.05035
[5] N.Alon, Combinatorial Nullstellensatz, Combin Probab Comput8 (1999), 7-29. · Zbl 0920.05026
[6] P. N.Balister, E.Győri, J.Lehel, and R. H.Schelp, Adjacent vertex distinguishing edge‐colorings, SIAM J Discrete Math21(1) (2007), 237-250. · Zbl 1189.05056
[7] T.Bohman and D.Kravitz, On the irregularity strength of trees, J Graph Theory45 (2004), 241-254. · Zbl 1034.05015
[8] M.Bonamy, N.Bousquet, and H.Hocquard, Adjacent vertex‐distinguishing edge coloring of graphs, Proceedings of The Seventh European Conference on Combinatorics, Graph Theory and Applications, Scuola Normale Superiore, 2013, pp. 313-318. · Zbl 1291.05055
[9] G.Chartrand, M. S.Jacobson, J.Lehel, O. R.Oellermann, S.Ruiz, and F.Saba, Irregular networks, Congr Numer64 (1988), 197-210. · Zbl 0671.05060
[10] G.Chartrand, P.Erdős, and O. R.Oellermann, How to define an irregular graph, College Math J19(1) (1988), 36-42. · Zbl 0995.05516
[11] B.Cuckler and F.Lazebnik, Irregularity strength of dense graphs, J Graph Theory58(4) (2008), 299-313. · Zbl 1188.05112
[12] A.Dong and G.Wang, Neighbor sum distinguishing colorings of some graphs, Discrete Math Algorithms Appl4(3) (2012), 1250047. · Zbl 1257.05040
[13] R. J.Faudree and J.Lehel, Bound on the irregularity strength of regular graphs, Colloq Math Soc Jańos Bolyai, 52, Combinatorics, Eger North Holland, Amsterdam, 1987, pp. 247-256. · Zbl 0697.05048
[14] E.Flandrin, A.Marczyk, J.Przybyło, J.‐F.Saclé, and M.Woźniak, Neighbor sum distinguishing index, Graphs Combin29(5) (2013), 1329-1336. · Zbl 1272.05047
[15] A.Frieze, R. J.Gould, M.Karoński, and F.Pfender, On graph irregularity strength, J Graph Theory41(2) (2002), 120-137. · Zbl 1016.05045
[16] C.Greenhill and A.Ruciński, Neighbour‐distinguishing edge colourings of random regular graphs, Electron J Combin13 (2006), #R77. · Zbl 1097.05035
[17] H.Hatami, \( \operatorname{\Delta} + 300\) is a bound on the adjacent vertex distinguishing edge chromatic number, J Combin Theory Ser B95 (2005), 246-256. · Zbl 1075.05034
[18] H.Hocquard and M.Montassier, Adjacent vertex‐distinguishing edge coloring of graphs with maximum degree Δ, J Combin Optim26(1) (2013), 152-160. · Zbl 1276.90079
[19] M.Horňák, D.Huang, and W.Wang, On neighbor‐distinguishing index of planar graphs, J Graph Theory76(4) (2014), 262-278. · Zbl 1296.05072
[20] M.Kalkowski, M.Karoński, and F.Pfender, Vertex‐coloring edge‐weightings: Towards the 1‐2‐3 conjecture, J Combin Theory Ser B100 (2010), 347-349. · Zbl 1209.05087
[21] M.Kalkowski, M.Karoński, and F.Pfender, A new upper bound for the irregularity strength of graphs, SIAM J Discrete Math25(3) (2011), 1319-1321. · Zbl 1237.05183
[22] M.Karoński, T.Łuczak, and A.Thomason, Edge weights and vertex colours, J Combin Theory Ser B91 (2004), 151-157. · Zbl 1042.05045
[23] J.Lehel, Facts and quests on degree irregular assignments, In: Graph Theory, Combinatorics and Applications, Wiley, New York, 1991, pp. 765-782. · Zbl 0841.05052
[24] P.Majerski and J.Przybyło, On the irregularity strength of dense graphs, SIAM J Discrete Math28(1) (2014), 197-205. · Zbl 1293.05341
[25] T.Nierhoff, A tight bound on the irregularity strength of graphs, SIAM J Discrete Math13 (2000), 313-323. · Zbl 0947.05067
[26] J.Przybyło, Irregularity strength of regular graphs, Electron J Combin15(1) (2008), #R82. · Zbl 1163.05329
[27] J.Przybyło, Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J Discrete Math23(1) (2009), 511-516. · Zbl 1216.05135
[28] J.Przybyło, Neighbor distinguishing edge colorings via the Combinatorial Nullstellensatz, SIAM J Discrete Math27(3) (2013), 1313-1322. · Zbl 1290.05079
[29] J.Przybyło, Asymptotically optimal neighbour sum distinguishing colourings of graphs, Random Struct Algor47 (2015), 776-791. · Zbl 1331.05083
[30] J.Przybyło and T.‐L.Wong, Neighbor distinguishing edge colorings via the Combinatorial Nullstellensatz revisited, J Graph Theory80(4) (2015), 299-312. · Zbl 1330.05075
[31] G.Wang, Z.Chen, and J.Wang, Neighbor sum distinguishing index of planar graphs, Discrete Math334 (2014), 70-73. · Zbl 1298.05136
[32] G.Wang and G.Yan, An improved upper bound for the neighbor sum distinguishing index of graphs, Discrete Appl Math175 (2014), 126-128. · Zbl 1297.05093
[33] T.Wang and Q.Yu, On vertex‐coloring 13‐edge‐weighting, Front Math China3 (2008), 1-7. · Zbl 1191.05048
[34] W.Wang and Y.Wang, Adjacent vertex distinguishing edge‐colorings of graphs with smaller maximum average degree, J Combin Optim19 (2010), 471-485. · Zbl 1221.05166
[35] Z.Zhang, L.Liu, and J.Wang, Adjacent strong edge coloring of graphs, Appl Math Lett15 (2002), 623-626. · Zbl 1008.05050
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.