×

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
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Addario-Berry, Vertex-colouring edge-weightings, Combinatorica 27 (1) pp 1– (2007) · Zbl 1127.05034 · doi:10.1007/s00493-007-0041-6
[2] Addario-Berry, Degree constrained subgraphs, Discrete Appl Math 156 (7) pp 1168– (2008) · Zbl 1147.05055 · doi:10.1016/j.dam.2007.05.059
[3] Aigner, Irregular assignments of trees and forests, SIAM J Discrete Math 3 pp 439– (1990) · Zbl 0735.05049 · doi:10.1137/0403038
[4] Akbari, r-Strong edge colorings of graphs, Discrete Math 306 pp 3005– (2006) · Zbl 1112.05035 · doi:10.1016/j.disc.2004.12.027
[5] Alon, Combinatorial Nullstellensatz, Combin Probab Comput 8 pp 7– (1999) · Zbl 0920.05026 · doi:10.1017/S0963548398003411
[6] Balister, Adjacent vertex distinguishing edge-colorings, SIAM J Discrete Math 21 (1) pp 237– (2007) · Zbl 1189.05056 · doi:10.1137/S0895480102414107
[7] Bohman, On the irregularity strength of trees, J Graph Theory 45 pp 241– (2004) · Zbl 1034.05015 · doi:10.1002/jgt.10158
[8] M. Bonamy N. Bousquet H. Hocquard Adjacent vertex-distinguishing edge coloring of graphs Proceedings of The Seventh European Conference on Combinatorics, Graph Theory and Applications 2013 313 318 · Zbl 1291.05055
[9] Chartrand, Irregular networks, Congr Numer 64 pp 197– (1988) · Zbl 0671.05060
[10] Chartrand, How to define an irregular graph, College Math J 19 (1) pp 36– (1988) · Zbl 0995.05516 · doi:10.2307/2686701
[11] Cuckler, Irregularity strength of dense graphs, J Graph Theory 58 (4) pp 299– (2008) · Zbl 1188.05112 · doi:10.1002/jgt.20313
[12] Dong, Neighbor sum distinguishing colorings of some graphs, Discrete Math Algorithms Appl 4 (3) pp 1250047– (2012) · Zbl 1257.05040 · doi:10.1142/S1793830912500474
[13] Faudree, Colloq Math Soc Jańos Bolyai, 52, Combinatorics pp 247– (1987)
[14] Flandrin, Neighbor sum distinguishing index, Graphs Combin 29 (5) pp 1329– (2013) · Zbl 1272.05047 · doi:10.1007/s00373-012-1191-x
[15] Frieze, On graph irregularity strength, J Graph Theory 41 (2) pp 120– (2002) · Zbl 1016.05045 · doi:10.1002/jgt.10056
[16] Greenhill, Neighbour-distinguishing edge colourings of random regular graphs, Electron J Combin 13 pp #R77– (2006) · Zbl 1097.05035
[17] Hatami, {\(\Delta\)}+300 is a bound on the adjacent vertex distinguishing edge chromatic number, J Combin Theory Ser B 95 pp 246– (2005) · Zbl 1075.05034 · doi:10.1016/j.jctb.2005.04.002
[18] Hocquard, Adjacent vertex-distinguishing edge coloring of graphs with maximum degree {\(\Delta\)}, J Combin Optim 26 (1) pp 152– (2013) · Zbl 1276.90079 · doi:10.1007/s10878-011-9444-9
[19] Horňák, On neighbor-distinguishing index of planar graphs, J Graph Theory 76 (4) pp 262– (2014) · Zbl 1296.05072 · doi:10.1002/jgt.21764
[20] Kalkowski, Vertex-coloring edge-weightings: Towards the 1-2-3 conjecture, J Combin Theory Ser B 100 pp 347– (2010) · Zbl 1209.05087 · doi:10.1016/j.jctb.2009.06.002
[21] Kalkowski, A new upper bound for the irregularity strength of graphs, SIAM J Discrete Math 25 (3) pp 1319– (2011) · Zbl 1237.05183 · doi:10.1137/090774112
[22] Karoński, Edge weights and vertex colours, J Combin Theory Ser B 91 pp 151– (2004) · Zbl 1042.05045 · doi:10.1016/j.jctb.2003.12.001
[23] Lehel, Graph Theory, Combinatorics and Applications pp 765– (1991)
[24] Majerski, On the irregularity strength of dense graphs, SIAM J Discrete Math 28 (1) pp 197– (2014) · Zbl 1293.05341 · doi:10.1137/120886650
[25] Nierhoff, A tight bound on the irregularity strength of graphs, SIAM J Discrete Math 13 pp 313– (2000) · Zbl 0947.05067 · doi:10.1137/S0895480196314291
[26] Przybyło, Irregularity strength of regular graphs, Electron J Combin 15 (1) pp #R82– (2008) · Zbl 1281.05058
[27] Przybyło, Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J Discrete Math 23 (1) pp 511– (2009) · Zbl 1216.05135 · doi:10.1137/070707385
[28] Przybyło, Neighbor distinguishing edge colorings via the Combinatorial Nullstellensatz, SIAM J Discrete Math 27 (3) pp 1313– (2013) · Zbl 1290.05079 · doi:10.1137/120880586
[29] Przybyło, Asymptotically optimal neighbour sum distinguishing colourings of graphs, Random Struct Algor 47 pp 776– (2015) · Zbl 1331.05083 · doi:10.1002/rsa.20553
[30] Przybyło, Neighbor distinguishing edge colorings via the Combinatorial Nullstellensatz revisited, J Graph Theory 80 (4) pp 299– (2015) · Zbl 1330.05075 · doi:10.1002/jgt.21852
[31] Wang, Neighbor sum distinguishing index of planar graphs, Discrete Math 334 pp 70– (2014) · Zbl 1298.05136 · doi:10.1016/j.disc.2014.06.027
[32] Wang, An improved upper bound for the neighbor sum distinguishing index of graphs, Discrete Appl Math 175 pp 126– (2014) · Zbl 1297.05093 · doi:10.1016/j.dam.2014.05.013
[33] Wang, On vertex-coloring 13-edge-weighting, Front Math China 3 pp 1– (2008) · Zbl 1191.05048 · doi:10.1007/s11461-008-0009-8
[34] Wang, Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree, J Combin Optim 19 pp 471– (2010) · Zbl 1221.05166 · doi:10.1007/s10878-008-9178-5
[35] Zhang, Adjacent strong edge coloring of graphs, Appl Math Lett 15 pp 623– (2002) · Zbl 1008.05050 · doi:10.1016/S0893-9659(02)80015-5
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.