×

Neighbor sum distinguishing total coloring of graphs with bounded treewidth. (English) Zbl 1396.05039

In this paper, the authors discuss the neighbor sum distinguishing total chromatic number of a graph \(G.\) The neighbor sum distinguishing total chromatic number is denoted by \(\chi^t_{\sum}(G)\). M. Pilśniak and M. Woźniak [Graphs Comb. 31, No. 3, 771–782 (2015; Zbl 1312.05054)] conjectured that for any graph \(G\), \(\chi^t_{\sum}(G)\leq \Delta(G)+3\). In this paper, the authors show that if a graph \(G\) has treewidth \(\ell \geq 3\) and \(\Delta(G)\geq 2 \ell+3\), then \(\chi^t_{\sum}(G)\leq \Delta(G)+ \ell-1\). Through this they prove the conjecture for graphs whose treewidth is \(3\) and \(4\). The authors also prove for \(\ell=3\) and \(\Delta \geq 9\), that \(\Delta(G)+1\leq \chi^t_{\sum}(G)\leq \Delta(G)+2\) and show when the equality is valid and characterize such graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)

Citations:

Zbl 1312.05054
Full Text: DOI

References:

[1] Alon, N, Combinatorial nullstellensatz, Comb Probab Comput., 8, 7-29, (1999) · Zbl 0920.05026 · doi:10.1017/S0963548398003411
[2] Bodlaender, HL, A partial \(k\)-arboretum of graphs with bounded treewidth, Theor Comput Sci, 209, 1-45, (1998) · Zbl 0912.68148 · doi:10.1016/S0304-3975(97)00228-4
[3] Bondy JA, Murty USR (2008) Graph theory. In: GTM, vol 244. Springer, Berlin · Zbl 1250.05093
[4] Bruhn, H; Lang, R; Stein, M, List edge-coloring and total coloring in graphs of low treewidth, J Graph Theory, 81, 272-282, (2016) · Zbl 1339.05114 · doi:10.1002/jgt.21874
[5] Dong, AJ; Wang, GH, Neighbor sum distinguishing total coloring of graphs with bounded maximum average degree, Acta Math Sin, 30, 703-709, (2014) · Zbl 1408.05061 · doi:10.1007/s10114-014-2454-7
[6] Ding, LH; Wang, GH; Yang, GY, Neighbor sum distinguishing total coloring via the combinatorial nullstellensatz, Sin China Ser Math, 57, 1875-1882, (2014) · Zbl 1303.05058 · doi:10.1007/s11425-014-4796-0
[7] Kalkowski M (2009) A note on 1,2-conjecture, in Ph.D. Thesis · Zbl 1306.05066
[8] 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
[9] Karoński, M; Łuczak, T; Thomason, A, Edge weights and vertex colours, J Comb Theory Ser B, 91, 151-157, (2004) · Zbl 1042.05045 · doi:10.1016/j.jctb.2003.12.001
[10] Lang R (2015) On the list chromatic index of graphs of tree-width 3 and maximum degree 7. arXiv:1504.02122 · Zbl 1042.05045
[11] Li, HL; Liu, BQ; Wang, GH, Neighbor sum distinguishing total coloring of \(K_4\)-minor-free graphs, Front Math China, 8, 1351-1366, (2013) · Zbl 1306.05066 · doi:10.1007/s11464-013-0322-x
[12] Li, HL; Ding, LH; Liu, BQ; Wang, GH, Neighbor sum distinguishing total colorings of planar graphs, J Comb Optim, 30, 675-688, (2015) · Zbl 1325.05083 · doi:10.1007/s10878-013-9660-6
[13] Lu Y, Han M, Luo R (2018) Neighbor sum distinguishing total coloring and list neighbor sum distinguishing total coloring. Discrete Appl Math 237:109-115 · Zbl 1380.05076
[14] Meeks, K; Scott, A, The parameterised complexity of List problems on graphs of bounded treewidth, Inf Comput, 251, 91-103, (2016) · Zbl 1353.68134 · doi:10.1016/j.ic.2016.08.001
[15] Pilśniak, M; Woźniak, M, On the total-neighbor distinguishing index by sums, Graphs Comb, 31, 771-782, (2015) · Zbl 1312.05054 · doi:10.1007/s00373-013-1399-4
[16] Przybyło, J; Woźniak, M, On a 1,2 conjecture, Discrete Math Theor Comput Sci, 12, 101-108, (2010) · Zbl 1250.05093
[17] Yao, JJ; Yu, XW; Wang, GH; Xu, CQ, Neighbor sum (set) distinguishing total choosability of \(d\)-degenerate graphs, Graphs Comb, 32, 1611-1620, (2016) · Zbl 1342.05052 · doi:10.1007/s00373-015-1646-y
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.