×

zbMATH — the first resource for mathematics

Group sum chromatic number of graphs. (English) Zbl 1333.05100
Summary: We investigate the group sum chromatic number (\(\chi_g^\varSigma(G)\)) of graphs, i.e. the smallest value \(s\) such that taking any abelian group \(\mathcal{G}\) of order \(s\), there exists a function \(f : E(G) \to \mathcal{G}\) such that the sums of edge labels properly colour the vertices. It is known that \(\chi_g^\varSigma(G) \in \{\chi(G), \chi(G) + 1 \}\) for any graph \(G\) with no component of order less than \(3\) and we characterize the graphs for which \(\chi_g^\varSigma(G) = \chi(G)\).

MSC:
05C15 Coloring of graphs and hypergraphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Addario-Berry, L.; Dalal, K.; McDiarmid, C.; Reed, B. A.; Thomason, A., Vertex-colouring edge-weightings, Combinatorica, 27, 1-12, (2007) · Zbl 1127.05034
[2] Addario-Berry, L.; Dalal, K.; Reed, B. A., Degree constrainted subgraphs, Discrete Appl. Math., 156, 1168-1174, (2008) · Zbl 1147.05055
[3] Beals, R.; Gallian, J.; Headley, P.; Jungreis, D., Harmonious groups, J. Combin. Theory Ser. A, 56, 223-238, (1991) · Zbl 0718.20013
[4] Cavenagh, N.; Combe, D.; Nelson, A. M., Edge-magic group labellings of countable graphs, Electron. J. Combin., 13, #R92, (2006), 19 pp · Zbl 1111.05085
[5] Combe, D.; Nelson, A. M.; Palmer, W. D., Magic labellings of graphs over finite abelian groups, Australas. J. Combin., 29, 259-271, (2004) · Zbl 1050.05107
[6] Froncek, D., Group distance magic labeling of Cartesian products of cycles, Australas. J. Combin., 55, 167-174, (2013) · Zbl 1278.05210
[7] Gallian, J. A., A dynamic survey of graph labeling, Electron. J. Combin., (2015), DS6,http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6
[8] Graham, R. L.; Sloane, N. J.A., On additive bases and harmonious graphs, SIAM J. Algebr. Discrete Methods, 1, 382-404, (1980) · Zbl 0499.05049
[9] Hovey, M., \(A\)-cordial graphs, Discrete Math., 93, 183-194, (1991) · Zbl 0753.05059
[10] Kalkowski, M., A note on 1,2-conjecture, (2009), (Ph.D. Thesis)
[11] 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
[12] Kaplan, G.; Lev, A.; Roditty, Y., On zero-sum partitions and anti-magic trees, Discrete Math., 309, 2010-2014, (2009) · Zbl 1229.05031
[13] Karoński, M.; Łuczak, T.; Thomason, A., Edge weights and vertex colours, J. Combin. Theory Ser. B, 91, 151-157, (2004) · Zbl 1042.05045
[14] Lu, H.; Yu, Q.; Zhang, C.-Q., Vertex-coloring 2-edge-weighting of graphs, European J. Combin., 32, 21-27, (2011) · Zbl 1203.05056
[15] Stanley, R. P., Linear homogeneous Diophantine equations and magic labelings of graphs, Duke Math. J., 40, 607-632, (1973) · Zbl 0269.05109
[16] Wang, T.; Yu, Q., On vertex-coloring 13-edge-weighting, Front. Math. China, 3, 581-587, (2008) · Zbl 1191.05048
[17] Żak, A., Harmonious orders of graphs, Discrete Math., 309, 6055-6064, (2009) · Zbl 1188.05138
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.