Neighbor sum distinguishing index of \(K_4\)-minor free graphs. (English) Zbl 1342.05053
Summary: A proper \([k]\)-edge coloring of a graph \(G\) is a proper edge coloring of \(G\) using colors from \([k]=\{1,2,\dots,k\}\). A neighbor sum distinguishing \([k]\)-edge coloring of \(G\) is a proper \([k]\)-edge coloring of \(G\) such that for each edge \(uv\in E(G)\), the sum of colors taken on the edges incident to \(u\) is different from the sum of colors taken on the edges incident to \(v\). By \(\mathrm{nsdi}(G)\), we denote the smallest value \(k\) in such a coloring of \(G\). It was conjectured by E. Flandrin et al. [Graphs Comb. 29, No. 5, 1329–1336 (2013; Zbl 1272.05047)] that if \(G\) is a connected graph with at least three vertices and \(G\neq C_5\), then \(\mathrm{nsdi}(G)\leq\varDelta (G)+2\). In this paper, we prove that this conjecture holds for \(K_4\)-minor free graphs, moreover if \(\varDelta (G)\geq 5\), we show that nsdi\((G)\leq\varDelta (G)+1\). The bound \(\varDelta (G)+1\) is sharp.
Citations:
Zbl 1272.05047References:
| [1] | Addario-Berry, L., Dalal, K., McDiarmid, C., Reed, B.A., Thomason, A.: Vertex-coloring edge-weightings. Combintorica 27, 1-12 (2007) · Zbl 1127.05034 · doi:10.1007/s00493-007-0041-6 |
| [2] | Addario-Berry, L., Dalal, K., Reed, B.A.: Degree constrained subgraphs. Discrete Appl. Math. 156, 1168-1174 (2008) · Zbl 1147.05055 · doi:10.1016/j.dam.2007.05.059 |
| [3] | Akbari, S., Bidkhori, H., Nosrati, \[N.: r\] r-Strong edge colorings of graphs. Discrete Math. 306, 3005-3010 (2006) · Zbl 1112.05035 · doi:10.1016/j.disc.2004.12.027 |
| [4] | Balister, P.N., Győri, E., Lehel, J., Schelp, R.H.: Adjacent vertex distinguishing edge-colorings. SIAM J. Discrete Math. 21, 237-250 (2007) · Zbl 1189.05056 · doi:10.1137/S0895480102414107 |
| [5] | Bonamy, M., Przybyło, J.: On the neighbor sum distinguishing index of planar graphs. arXiv:1408.3190 · Zbl 1367.05066 |
| [6] | Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer-Verlag, London (2008) · Zbl 1134.05001 · doi:10.1007/978-1-84628-970-5 |
| [7] | Bu, Y., Lih, K., Wang, W.: Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six. Discussiones Mathematicae Graph Theory 31-3, 429-439 (2011) · Zbl 1229.05100 · doi:10.7151/dmgt.1556 |
| [8] | Chartrand, G., Harary, F.: Planar permutation graphs. Ann. Inst. H. Poincaré Sect. B (N.S.) 3, 433-438 (1967) · Zbl 0162.27605 |
| [9] | Dong, A., Wang, G., Zhang, J.: Neighbor sum distinguishing colorings of graphs with bounded maximum average degree. Discrete Appl. Math. 30-4, 703-709 (2014) · Zbl 1408.05061 |
| [10] | Edwards, K., Horn̆ák, M., Woźniak, 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 |
| [11] | Flandrin, E., Marczyk, A., Przybyło, J., Saclé, J.-F., Woźniak, M.: Neighbor sum distinguishing index. Graphs Comb. 29-5, 1329-1336 (2013) · Zbl 1272.05047 · doi:10.1007/s00373-012-1191-x |
| [12] | Hatami, \[H.: \Delta\] Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number. J. Comb. Theory Ser. B 95, 246-256 (2005) · Zbl 1075.05034 · doi:10.1016/j.jctb.2005.04.002 |
| [13] | Horn̆ák, M., Huang, D., Wang, W.: On neighbour-distinguishing index of planar graphs. J. Graph Theory 76—-4, 262-278 (2014) · Zbl 1296.05072 · doi:10.1002/jgt.21764 |
| [14] | Kalkowski, M., Karoński, M., Pfender, F.: Vertex-coloring edge-weightings: towards the 1-2-3-conjecture. J. Comb. Theory Ser. B 100, 347-349 (2010) · Zbl 1209.05087 · doi:10.1016/j.jctb.2009.06.002 |
| [15] | Karoński, M., Łuczak, T., Thomason, A.: Edge weights and vertex colors. J. Comb. Theory Ser. B 91, 151-157 (2004) · Zbl 1042.05045 · doi:10.1016/j.jctb.2003.12.001 |
| [16] | Li, H., Ding, L. Liu, B., Wang, G.: Neighbor sum distinguishing total colorings of planar graphs. J. Comb. Optim. doi:10.1007/s10878-013-9660-6 · Zbl 1325.05083 |
| [17] | Przybyło, J.: Neighbor sum distinguishing colorings via the Combinatorial Nullstellensatz. SIAM J. Discrete Math. 27-3, 1313-1322 (2013) · Zbl 1290.05079 · doi:10.1137/120880586 |
| [18] | Wang, G., Chen, Z., Wang, J.: Neighbor sum distinguishing index of planar graphs. Discrete Math. 334, 70-73 (2014) · Zbl 1298.05136 · doi:10.1016/j.disc.2014.06.027 |
| [19] | Wang, G., Yan, G.: An improved upper bound for the neighbor sum distinguishing index of graphs. Discrete Appl. Math. 175, 126-128 (2014) · Zbl 1297.05093 · doi:10.1016/j.dam.2014.05.013 |
| [20] | Wang, W., Wang, Y.: Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree. J. Comb. Optim. 19, 471-485 (2010) · Zbl 1221.05166 · doi:10.1007/s10878-008-9178-5 |
| [21] | Wang, W., Wang, Y.: Adjacent vertex-distinguishing edge colorings of \[K_4\] K4-minor free graphs. Appl. Math. Lett. 24-12, 2034-2037 (2011) · Zbl 1234.05105 · doi:10.1016/j.aml.2011.05.038 |
| [22] | Wang, T., Yu, Q.: On vertex-coloring 13-edge-weighting. Front. Math. China 3, 581-587 (2008) · Zbl 1191.05048 · doi:10.1007/s11464-008-0041-x |
| [23] | Zhang, Z., Liu, L., Wang, J.: Adjacent strong edge coloring of graphs. J. Appl. Math. Lett. 15, 623-626 (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.
