×

zbMATH — the first resource for mathematics

Neighbour sum distinguishing total colourings via the combinatorial nullstellensatz. (English) Zbl 1330.05074
Summary: Consider a simple graph \(G=(V,E)\) and its (proper) total colouring \(c\) with elements of the set \(\{1,2,\dots,k\}\). We say that \(c\) is neighbour sum distinguishing if for every edge \(uv\in E\), the sums of colours met by \(u\) and \(v\) differ, i.e., \(c(u)+\sum_{e\ni u}c(e)\neq c(v)+\sum_{e\ni v}c(e)\). The least \(k\) guaranteeing the existence of such a colouring is denoted \(\chi^{\prime\prime}_\Sigma(G)\). We investigate a daring conjecture presuming that \(\chi^{\prime\prime}_\Sigma(G)\leq \Delta(G)+3\) for every graph \(G\), a seemingly demanding problem if confronted with up-to-date progress in research on the total colouring conjecture itself. We note that \(\chi^{\prime\prime}_\Sigma(G)\leq \delta(G)+2\mathrm{col}(G)-1\) and apply combinatorial nullstellensatz to prove a stronger bound: \(\chi^{\prime\prime}_\Sigma(G)\leq \delta (G)+\lceil 53\mathrm{col}(G)\rceil\). This imply an upper bound of the form \(\chi^{\prime\prime}_\Sigma(G)\leq \delta (G)+\mathrm{const.}\) for many classes of graphs with unbounded maximum degree. In particular we obtain \(\chi^{\prime\prime}_\Sigma(G)\leq \delta (G)+10\) for planar graphs. In fact we show that identical bounds also hold if we use any set of \(k\) real numbers instead of \(\{1,2,\dots,k\}\) as edge colours, and moreover the same is true in list versions of the both concepts.

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Addario-Berry, L.; Dalal, K.; McDiarmid, C.; Reed, B. A.; Thomason, A., Vertex-colouring edge-weightings, Combinatorica, 27, 1, 1-12, (2007) · Zbl 1127.05034
[2] Addario-Berry, L.; Dalal, K.; Reed, B. A., Degree constrained subgraphs, Discrete Appl. Math., 156, 7, 1168-1174, (2008) · Zbl 1147.05055
[3] Aigner, M.; Triesch, E., Irregular assignments of trees and forests, SIAM J. Discrete Math., 3, 4, 439-449, (1990) · Zbl 0735.05049
[4] Alon, N., Combinatorial nullstellensatz, Combin. Probab. Comput., 8, 7-29, (1999) · Zbl 0920.05026
[5] Bartnicki, T.; Grytczuk, J.; Niwczyk, S., Weight choosability of graphs, J. Graph Theory, 60, 3, 242-256, (2009) · Zbl 1210.05138
[6] Behzad, M., Graphs and their chromatic numbers, (1965), Michigan State University, (Ph.D. thesis)
[7] Bohman, T.; Kravitz, D., On the irregularity strength of trees, J. Graph Theory, 45, 241-254, (2004) · Zbl 1034.05015
[8] M. Bonamy, J. Przybyło, On the neighbour sum distinguishing index of planar graphs, submitted for publication. arXiv:1408.3190. · Zbl 1367.05066
[9] Chartrand, G.; Erdős, P.; Oellermann, O. R., How to define an irregular graph, College Math. J., 19, 1, 36-42, (1988) · Zbl 0995.05516
[10] Chartrand, G.; Jacobson, M. S.; Lehel, J.; Oellermann, O. R.; Ruiz, S.; Saba, F., Irregular networks, Congr. Numer., 64, 197-210, (1988)
[11] Cuckler, B.; Lazebnik, F., Irregularity strength of dense graphs, J. Graph Theory, 58, 4, 299-313, (2008) · Zbl 1188.05112
[12] Dinitz, J. H.; Garnick, D. K.; Gyárfás, A., On the irregularity strength of the \(m \times n\) grid, J. Graph Theory, 16, 355-374, (1992) · Zbl 0771.05055
[13] Dong, A.; Wang, G., Neighbor sum distinguishing colorings of some graphs, Discrete Math. Algorithms Appl., 4, 3, 1250047, (2012) · Zbl 1257.05040
[14] Erdős, P.; Rubin, A. L.; Taylor, H., Choosability in graphs, (Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, CA, 1979), Congress. Numer. XXVI, Utilitas Math., (1980), Winnipeg Man), 125-157
[15] Faudree, R. J.; Lehel, J., Bound on the irregularity strength of regular graphs, (Colloq Math Soc Jańos Bolyai, Combinatorics, vol. 52, (1987), Eger North Holland Amsterdam), 247-256
[16] Flandrin, E.; Marczyk, A.; Przybyło, J.; Sacle, J.-F.; Woźniak, M., Neighbor sum distinguishing index, Graphs Combin., 29, 5, 1329-1336, (2013) · Zbl 1272.05047
[17] Frieze, A.; Gould, R. J.; Karoński, M.; Pfender, F., On graph irregularity strength, J. Graph Theory, 41, 2, 120-137, (2002) · Zbl 1016.05045
[18] Gallian, J. A., Graph labeling, Electron. J. Combin., 1-308, (2013), Dynamic survey DS6
[19] Hatami, H., \(\Delta + 300\) is a bound on the adjacent vertex distinguishing edge chromatic number, J. Combin. Theory Ser. B, 95, 246-256, (2005) · Zbl 1075.05034
[20] Kalkowski, M., A note on 1,2-conjecture, Electron. J. Combin., (2015), in press
[21] Kalkowski, M.; Karoński, M.; Pfender, F., A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math., 25, 1319-1321, (2011) · Zbl 1237.05183
[22] Kalkowski, M.; Karoński, M.; Pfender, F., Vertex-coloring edge-weightings: towards the 1-2-3 conjecture, J. Combin. Theory Ser. B, 100, 347-349, (2010) · Zbl 1209.05087
[23] Karoński, M.; Łuczak, T.; Thomason, A., Edge weights and vertex colours, J. Combin. Theory Ser. B, 91, 151-157, (2004) · Zbl 1042.05045
[24] Lehel, J., Facts and quests on degree irregular assignments, (Graph Theory, Combinatorics and Applications, (1991), Willey New York), 765-782 · Zbl 0841.05052
[25] Li, H.; Ding, L.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim., 30, 3, 675-688, (2015) · Zbl 1325.05083
[26] Li, H.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of \(K_4\)-minor free graphs, Front. Math. China, 8, 6, 1351-1366, (2013) · Zbl 1306.05066
[27] Majerski, P.; Przybyło, J., On the irregularity strength of dense graphs, SIAM J. Discrete Math., 28, 1, 197-205, (2014) · Zbl 1293.05341
[28] Molloy, M.; Reed, B., A bound on the total chromatic number, Combinatorica, 18, 2, 241-280, (1998) · Zbl 0921.05033
[29] Nierhoff, T., A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math., 13, 3, 313-323, (2000) · Zbl 0947.05067
[30] Pilśniak, M.; Woźniak, M., On the total-neighbor-distinguishing index by sums, Graphs Combin., 31, 3, 771-782, (2015) · Zbl 1312.05054
[31] Przybyło, J., Asymptotically optimal neighbour sum distinguishing colourings of graphs, Random Structures Algorithms, (2015), in press, http://dx.doi.org/10.1002/rsa.20553 · Zbl 1331.05083
[32] Przybyło, J., Irregularity strength of regular graphs, Electron. J. Combin., 15, 1, ♯R82, (2008) · Zbl 1163.05329
[33] Przybyło, J., Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. Discrete Math., 23, 1, 511-516, (2009) · Zbl 1216.05135
[34] Przybyło, J., Neighbor distinguishing edge colorings via the combinatorial nullstellensatz, SIAM J. Discrete Math., 27, 3, 1313-1322, (2013) · Zbl 1290.05079
[35] Przybyło, J.; Wong, T.-L., Neighbor distinguishing edge colorings via the combinatorial nullstellensatz revisited, J. Graph Theory, (2015), in press, http://dx.doi.org/10.1002/jgt.21852 · Zbl 1330.05075
[36] Przybyło, J.; Woźniak, M., On a 1,2 conjecture, Discrete Math. Theor. Comput. Sci., 12, 1, 101-108, (2010) · Zbl 1250.05093
[37] Przybyło, J.; Woźniak, M., Total weight choosability of graphs, Electron. J. Combin., 18, 1, ♯P112, (2011) · Zbl 1217.05202
[38] B. Seamone, The 1-2-3 Conjecture and related problems: a survey, submitted for publication. arXiv:1211.5122.
[39] Vizing, V., Coloring the vertices of a graph in prescribed colors, Diskret Analiz Metody Diskret Anal v Teorii Kodov i Shem, 101, 3-10, (1976), (in Russian)
[40] Vizing, V., Some unsolved problems in graph theory, Russian Math. Surveys, 23, 125-141, (1968) · Zbl 0192.60502
[41] Wang, G.; Chen, Z.; Wang, J., Neighbor sum distinguishing index of planar graphs, Discrete Math., 334, 70-73, (2014) · Zbl 1298.05136
[42] Wong, T.-L.; Zhu, X., Every graph is (2,3)-choosable, Combinatorica, (2015), in press, http://dx.doi.org/10.1007/s00493-014-3057-8
[43] Wong, T.-L.; Zhu, X., Total weight choosability of graphs, J. Graph Theory, 66, 198-212, (2011) · Zbl 1228.05161
[44] Zhang, Z.; Liu, L.; Wang, J., Adjacent strong edge coloring of graphs, Appl. Math. Lett., 15, 623-626, (2002) · 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. 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.