On twin edge colorings in m-ary trees

Jayson De Luna Tolentino, Reginaldo M. Marcelo, Mark Anthony C. Tolentino


Let k ≥ 2 be an integer and G be a connected graph of order at least 3. A twin k-edge coloring of G is a proper edge coloring of G that uses colors from ℤk and that induces a proper vertex coloring on G where the color of a vertex v is the sum (in ℤk) of the colors of the edges incident with v. The smallest integer k for which G has a twin k-edge coloring is the twin chromatic index of G and is denoted by χt(G). In this paper, we study the twin edge colorings in m-ary trees for m ≥ 2; in particular, the twin chromatic indexes of full m-ary trees that are not stars, r-regular trees for even r ≥ 2, and generalized star graphs that are not paths nor stars are completely determined. Moreover, our results confirm the conjecture that χt(G)≤Δ(G)+2 for every connected graph G (except C5) of order at least 3, for all trees of order at least 3.


edge coloring, vertex coloring, m-ary trees

Full Text:


DOI: http://dx.doi.org/10.5614/ejgta.2022.10.1.8


S. Anantharaman, Twin edge coloring of total graph and graphs with twin chromatic index ∆ + 2, Appl. Appl. Math., 15 (2020), 314 – 336.

E. Andrews, L. Helenius, D. Johnston, J. VerWys, and P. Zhang, On twin edge colorings of graphs, Discuss. Math. Graph Theory, 34 (2014), 613 – 627.

E. Andrews, D. Johnston, and P. Zhang, A twin edge coloring conjecture, Bull. Inst. Combin. Appl., 70 (2014), 28 – 44.

E. Andrews, D. Johnston, and P. Zhang, On twin edge colorings in trees, J. Combin. Math. Combin. Comput., 94 (2015), 115 – 131.

S. Lakshmi and V. Kowsalya, Twin edge colourings of wheel graphs, IOSR J. Math., 12 (2016), 71 – 73.

R. Rajarajachozhan and R. Sampathkumar, Twin edge colorings of certain square graphs and product graphs, Electron. J. Graph Theory Appl., 4 (1) (2016), 79 – 93.

J. Tolentino, R. Marcelo, and M.A. Tolentino, Twin chromatic indices of some graphs with maximum degree 3, J. Phys.: Conf. Ser., 1538 (2020).

H. Yang, S.L. Tian, and L.W.Q. Suo, On twin edge colorings of the direct product of paths, J. Phys.: Conf. Ser., 1087 (2018).

P. Zhang, Color Induced Graph Colorings, Springer, New York, 2015.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats