Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 494 https://internationalpubls.com On Total Coloring of Triple Star and Lobster Graphs A. Punitha1, G. Jayaraman2* 1,2Department of Mathematics, 1,2 Vels Institute of Science, Technology and Advanced Studies (VISTAS), Pallavaram, Chennai-117, India.*Corresponding author Email: jayaram07maths@gmail.com Article History: Received: 11-05-2024 Revised: 25-06-2024 Accepted: 12-07-2024 Abstract A k-total coloring of a graph G is an assignment of k colors to the elements (vertices and edges) of G such that adjacent or incident elements have different colors. The total chromatic number is the smallest integer k for which G has a k-total coloring. The well- known Total Coloring Conjecture asserts that the total chromatic number of a graph is either ∆(G) + 1 or ∆(G) + 2, where ∆(G) is the maximum degree of G. In this paper, we consider the triple star graph, lobster graph and its line, middle, total graphs and also splitting graph of triple star. We obtained the preceding graphs has total chromatic number equal to ∆(G) + 1. Keywords: Total coloring, total chromatic number, triple star graph, lobster graph, line, middle, total, splitting graph. AMS subject classification: 05C15. 1. Introduction The graph described is finite, undirected, and has no loops or multiple edges. A k -total coloring is an assignment of k colors to the elements (ie, vertices and edges) of G , for which two adjacent or incident elements have distinct colors. The total chromatic number '' ( )G , is the least k , for which G has a k -total coloring. Behzad [2] and vizing [17] independently, suggested the famous conjecture, known as TCC: for any graph ,G ''( ) 1 ( ) ( ) 2.G G G +    + This conjecture was authenticated by Rosenfeld [15] and Vijayadithya [16] for 3, = and by kostochka [8, 9] for 5. This result was firstly given in [3] for 14. In [10], this result was protracted to 9. A survey paper on total coloring would likely include a comprehensive collection of articles covering various aspects of total coloring [4]. Jayaraman et al. [7, 11, 12, 13, 14] discussed the total coloring of line, middle, total and splitting graph of double star graph, snake graph families, splitting graph of path, cycle and star graph and certain convex polytope graphs Total coloring provides a powerful tool for modeling and solving various practical problems arising in scheduling, wireless networks, telecommunications. In [1], the author has extended the concept of the double star graph to introduce the triple star graph. In this paper, we obtained the total chromatic number of triple star, lobster graph and its line, middle, total graph and also splitting graph of triple star graph. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 495 https://internationalpubls.com 2. Preliminaries Definition 2.1 Triple star graph 1, , ,K    = [1] is constructed from the double star graph 1, ,K   by adding a new pendent edge to each existing pendant node, then it forms a tree structure. It has 3 1 + nodes and 3 edges. Definition 2.2. The lobster graph (2, )L r  = [6] is constructed by the path on  nodes as a backbone. Each node in the backbone is attached to two distinct node hands, and each node hand is connected to r distinct node fingers, each of which has degree one, throughout this article, we take 1.r = Definition 2.3. The line graph ( )L G [7] has nodes that are edges of ,G and two nodes in ( )L G are adjacent, whenever their edges are adjacent in .G Definition 2.4. The middle graph ( )M G [5, 13] is formed by subdividing each edge exactly once and connecting these newly obtained nodes of adjacent edges of .G Definition 2.5. The total graph ( )T G [13] is a middle graph, adding an edge between the vertices whenever they are adjacent in G . Definition 2.6. The splitting graph ( )S G [12] is obtained by adding a new vertex 'v corresponding to each vertex v of G such that '( ) ( ).N v N v= Lemma 2.7. [18] For any simple graph ,G ''( ) ( ) 1.G G   + Theorem 2.8. [18] Let nK be the complete graph, then '' , ( ) 1, n n if n is odd K n if n is even   =  + 3. Results and Discussion Theorem 3.1. For any 4  , '' ( ) 1  = + . Proof: Let ( ) { } { :1 } { ;1 } { ;1 }V u u v w         =       , where u is the root vertex of the triple star graph. ( ) { , , :1 }E e uu f u v e v w          = = = =   Define total coloring  , such that : ( ) ( ) {1,2,3,..., 1}V E    → + For 1    ( ) 1u = + ; ( ) ( ) 1(mod )u w    = = + ; ( ) 4(mod )v  = + ; ( ) ( ) (mod )e g    = = ; ( ) 3(mod )f  = + By this procedure, the graph  is attained with 1 + total colorable. So, it is clear that '' ( ) 1.   + Since ( )  = and by lemma 2.7, it follows that ''( ) ( ) 1     + 1. + Therefore '' ( ) 1.  = + Equivalently, this is true for all other values of 4.  Hence '' ( ) 1.  = + Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 496 https://internationalpubls.com Fig 1: Total coloring of triple star graph 7 Theorem 3.2: For any 4  , ''( ( )) 1L   = + . Proof: Let ( ( )) { , , :1 }V L u v w     =   and ( ( )) { , :1 } { :1 , , 1 }E L u v v w u v               =      +   Define  , such that : ( ( )) ( ( )) {1,2,3,..., 1}.V L E L    → + ( ) , for all 1u   =   ; 1, 1, ( ) 1, 2 1 if v if         + = =  −   − ; 2 , 1 1 ( ) 1, if w if        +   − =  = 2 , 2 0 (mod 1) ( ) 1, otherwise if u v        +  =  + ; ( ) , for all 1v w    =   ; , ( ) 0 (mod 1) ( ) 1, otherwise , 1 if u u              + +  +  =  +  +   Fig 2: Total coloring of 7( )L  By this procedure, the graph ( )L  is attained with 1 + total colorable. So, it is clear that ''( ( )) 1.L    + Since ( ( ))L   = and by lemma2.7, it follows that ''( ( )) ( ( )) 1L L     + 1. + Therefore ''( ( )) 1.L   = + Equivalently, this is true for all other values of 4.  Hence ''( ( )) 1.L   = + Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 497 https://internationalpubls.com Theorem 3.3: For any 4  , ''( ( )) 3.M   = + Proof:  ' ' '( ( )) { } { } { } { } { } { } { }:1V M v v v u u w w        =   and     ' ' ' ' ' ' ' ' ' ' ' ' ( ( )) ; ; ; ; ; ; ; :1 :1 1, 1 E M vv v v v u u u u w w w w u u v v v t                          =     − +   The vertices , (1 )u u    induced a clique of order 3 + in ( )M  . Define  , such that : ( ( )) ( ( )) {1,2,3..., 3}V M E M    → + . Consider the following two cases Case (i): When  is even, for 1    ( ) 3v = + ; ( ) 2, ( )v u    = + = ; '( )v = ; '( ) 1u = + ; '( ) 3w = + ; ( ) 2w = + ; ' , 1 ( ) 1, 2 v v        = =  −   ; '( )v u  = ; '( ) 3u u  = + ; '( ) 2u w  = − ; '( ) 3w w  = − ; ' '( ) 1w u  = − ; ' '( ) 2u v  = + '( ) 2 , 2 0 (mod 3) vv if   =  + ; ' ' , ( ) 0 (mod 3) 1,2,..., 1 ( ) 3, , 1 if for v v otherwise                + +  + −  =  +  +   Case (ii): When  is odd, for 1    ( ) 3v = + ; ( ) 2, ( )v u    = + = ; '( )v = ; '( ) 1u = + ; '( ) 3w = + ; ( ) 2w = + ; ' 3, 1 ( ) 1, 2 v v        + = =  −   ; '( )v u  = ; '( ) 2u u  = + ; '( ) 2u w  = − ; '( ) 3w w  = − ; ' '( ) 1w u  = − ; ' '( ) 2u v  = + ; '( ) 2 , 2 0 (mod 2) vv if   =  + ; ' ' , ( ) 0 (mod 2) 1,2,..., 1 ( ) 2, otherwise , 1 if for v v               + +  + −  =  +  +   Fig 3: Total coloring of 7( )M  Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 498 https://internationalpubls.com By this procedure, the graph ( )M  is attained with 3 + total colorable. So, it is clear that ''( ( )) 3.M    + Since ( ( ))M   = and by lemma 2.7, it follows that ''( ( )) ( ( )) 1M M     + 3. + Therefore ''( ( )) 3.M   = + Equivalently, this is true for all other values of 4.  Hence ''( ( )) 3.M   = + Theorem 3.4: For any 4  , ''( ( )) 2 1.T   = + Proof: Let  ' ' '( ( )) { } { , , } { , , }:1V T v u v w u v w        =   and     ' ' ' ' ' ' ' ' ' ' ' ' ( ( )) ; ; ; ; ; ; ; ; ; ; :1 :1 1, 1 E T vv v v v u u u u w w w w u u v u v vv w u v v                                =     − +   The vertices , (1 )u u    induced a clique of order 3 + in ( )T  . Define  , such that : ( ( )) ( ( )) {1,2,3..., 2 1}V T E T    → + . Fig 4: Total coloring of 7( )T  For 1    ( ) 2 1v = + ; '( )v = ; ( ) 2 ; ( )v u    = = ; ( ) 2 1w = + ; ' 2, 2 0 (mod 2) ( ) 2, if u otherwise       + +  +  =  + ; ' 1, 1 0 (mod 1) ( ) 1, if w otherwise       + +  +  =  + ; ' 2 , 2 0 (mod 2 ) ( ) 2 , if vv otherwise         =   ; ' 1 , +1+ 0 (mod 2 1) ( ) 2 1, if v v otherwise          + +  +  =  + ' ' , ( ) 0 (mod 2 1) 1 1 ( ) 2 1, , 1 if for v v otherwise                 + +  −   −  =  −  +   ; Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 499 https://internationalpubls.com ' 3 , +3+ 0 (mod 2 1) ( ) 2 1, if v u otherwise          + +  +  =  + ; ' 1, 1 0 (mod 1) ( ) 1, if u u otherwise        + +  +  =  + '( ) 2 1u w  = + ; '( ) 1w w  = ; 2 1, 2 1 0mod(2 1) ( ) 2 1, if vv otherwise       − −  −  =  − ; ' ' 2 , 2 0 mod(2 1) ( ) ( ) 2 1, if u v u v otherwise             + + + +  +  = =  + ; ' '( ) 2w u  = + ; ( ) 2w u  = + By this procedure, the graph ( )T  is attained with 2 1 + total colorable. So, it is clear that ''( ( )) 2 1.T    + Since ( ( ))T   = and by lemma 2.7, it follows that ''( ( )) ( ( )) 1T T     + 3. + Therefore ''( ( )) 2 1.T   = + Equivalently, this is true for all other values of 4.  Hence ''( ( )) 2 1.T   = + Theorem 3.5: For any 4  , ''( ( )) 2 1.S   = + Proof: Let  ' ' '( ( )) { } { , , } { , , }:1V S v u v w u v w        =   and  ' ' ' ' ' '( ( )) ; ; ; ; ; ; ; ; :1E S uu u u uu u v u v u v v w v w v w                 =   Define  , such that : ( ( )) ( ( )) {1,2,3...2 1}V S E S    → + . '( ) ( ) 2 1u u  = = + ; ' 1, ( 1) 0 (mod 1) ( ) ( ) 1, if u u otherwise         + +  +  = =  + ; '( ) ( ) 2v v   = = + ; '( ) ( ) 3w w   = = + , 0 (mod 2 ) ( ) 2 , if uu otherwise         + +   =   ; ' ' , 0 (mod ) ( ) ( ) , if uu u u otherwise           = =   ; 2 , 1 1 ( ) 2, if u v           − =  − = ; ( )v w  = ; ' '( ) ( ) 2 1u v u v     = = + ; '( ) 1v w  = ; '( ) 2v w  = Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 500 https://internationalpubls.com Fig 5: Total coloring of 7( )S  Based on the above procedure, the graph ( )S  is attained with 2 1 + total colorable. So, it is clear that ''( ( )) 2 1.S    + Since ( ( ))S   = and by lemma 2.7, it follows that ''( ( )) ( ( )) 1S S     + 3. + Therefore ''( ( )) 2 1.S   = + Similarly, this result is true for all values of 4.  Hence ''( ( )) 2 1.S   = + Theorem 3.6: let (2,1)L  = be the lobster, then '' ( ) 5.t  = Proof: let ' '( ) { , , , , :1 }V v u w w u       =   and ' '( ) { , , , :1 }E v u u u v w w w          =   1 { :1 1}v v   +   − Define : ( ) ( ) {1,2,3,4,5}V E    → as follows. The assigning of colors is given below: For 1    ( ) ( ) 2,1; 1,0 (mod 2)u v w if    = =  ; ( ) 1, 2; 1,0 (mod 2)v if =  ; ( ) 3,4; 1,0 (mod 2)w if =  ; ( ) 5v u  = ; '( ) 5w w  = ; '( ) 3u = ; '( ) 2w = ; '( ) 4u u  = For 1 1   − 1( ) 3,4; 1,0 (mod 2)v v if  + =  Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 501 https://internationalpubls.com Fig 6: Total coloring of lobster graph 5 Based on the above coloring approach, the graph  is total colored with 5 colors. Thus ''( ) 5.   Since ( ) 4 = and by lemma 2.7, '' ( ) ( ) 1 4 1 5     + = +  and hence ''( ) 5.  = Theorem 3.7: let ( )L  be the line graph of lobster graph, then '' ( ( )) 5.L   = Proof: let ' '( ( )) { , , , :1 } { :1 1}V L u w w u v         =     − and ' '( ( )) { , , :1 }E L u w u u w w        =   1 1{ , , , :1 1}.v u u v w v v w         + +   − Define : ( ( )) ( ( )) {1,2,3,4,5}V L E L    → as follows. The assigning of colors is given below: Fig 7: Total coloring of 5( )L  For 1    ( ) 1, 2; 1,0 (mod 2)u if =  ; '( ) 2,1; 1,0 (mod 2)u u if  =  ; ( ) 3w = ; '( ) 3u = ; '( ) 5w = ; '( ) 4w w  = For 1 1   − ( ) 5v = ; ( ) 3u v  = ; 1( ) 4v u  + = ; ( ) 1w v  = ; 1( ) 2v w  + = Hence  is a total coloring of ( )L  and therefore '' ( ( )) 5L    . Since ( ( ))L   = and by lemma 2.7, ''( ( )) ( ( )) 1 4 1 5L L     + = +  and '' ( ( )) 5.L   = Theorem 3.8: let ( )M  be the middle graph of lobster graph, then '' ( ( )) 9.M   = Proof: let ' '' ''' ' '' '''( ( )) { , , , , , , , , :1 } { :1 1}V M v u u u u w w w w x              =     − and ' ' '' '' ''' ' ' '' '' ''' '' ''( ( )) { , , , , , , , , , , :1 }E M v u u u u u u u v w w w w w w w u u u w w w                        =   1 1 1{ , , , , , :1 1}w x x w v x x v u x x y             + + +   − 1{ :1 2}x x   +   − . Define : ( ( )) ( ( )) {1,2,...9}V M E M    → as follows. The assigning of colors as noted below: Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 502 https://internationalpubls.com Fig 8: Total coloring of 5( )M  For 1    ( ) 1,2,3; 1, 2,0 (mod3)v if =  ; '( ) 1,2; 1,0 (mod 2)w if =  ; '''( ) 2w = ''( ) 5,6; 1,0 (mod 2)w if =  ; '''( ) 1u = ; ''( ) 9u = ; ( ) 6u = ; '( ) 8u = ; ( ) 9w = ; ( ) 7v u  = ; '( ) 4u u  = ; ' ''( ) 7u u  = ; '' '''( ) 5u u  = ; ( ) 6v w  = ; '( ) 5w w  = ; ' ''( ) 8w w  = '' '''( ) 4w w  = ; ''( ) 3u u  = ; ( ) 2u w  = ; ''( ) 3w w  = For 1 1   − ( ) 2,1,3; 1, 2,0 (mod3)x if =  ; ( ) 3,2,4; 1, 2,0 (mod 3)v x if  =  ; 1( ) 1,3,2; 1,2,0 (mod3)x v if  + =  ; ( ) 4w x  = ; 1( ) 7x w  + = ; ( ) 5u x  = ; 1( ) 6x u  + = For 1 2   − , 1( ) 8,9; 1,0 (mod 2)x x if  + =  Hence  is a total coloring of ( )M  and therefore '' ( ( )) 9M    . Since ( ( ))M   = and by lemma 2.7, ''( ( )) ( ( )) 1 8 1 9M M     + = +  and '' ( ( )) 9.tM  = Theorem 3.9: let ( )T  be the middle graph of lobster graph, then '' ( ( )) 9.T   = Proof: let ' '' ''' ' '' '''( ( )) { , , , , , , , , :1 } { :1 1}V T v u u u u w w w w x              =     − and ' ' '' '' ''' ' ' '' '' ''' '' ''' ' ' ' ' ''' '' 1 1 1 1 ( ( )) { , , , , , , , , , , , , , , :1 } { , , , , , , :1 1} E T v u u u u u u u v w w w w w w w u u u u u v v w w w u w w w u x v v x u w x x w v x x v                                                  + + + + =     − 1{ :1 2}x x   +   − . Define : ( ( )) ( ( )) {1,2,...9}V T E T    → as follows. The assigning of colors as noted below: Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 503 https://internationalpubls.com Fig 9: Total coloring of 5( )T  For 1    ( ) 1,2,3; 1, 2,0 (mod3)v if =  ; ( ) 6u = ; '( ) 5u = ; ''( ) 7u = ; '''( ) 1u = ; ( ) 9w = ; '( ) 4w = ; ''( ) 2w = ; '''( ) 1w = ; ( ) 7v u  = ; '( ) 8u u  = ; ' ''( ) 9u u  = ; '' '''( ) 8u u  = ; ( ) 5v w  = ; '( ) 1w w  = ; ' ''( ) 5w w  = ; '' '''( ) 7w w  = ; ''( ) 3u u  = ; ''' '( ) 2u u  = ; '( ) 4u v  = ; '( ) 6v w  = ; ' '''( ) 3w w  = ; ( ) 2u w  = ; ''( ) 3w w  = For 1 1   − ( ) 3,1,2; 1, 2,0 (mod3)x if =  ; ( ) 2,1,3; 1, 2,0 (mod 3)v x if  =  ; 1( ) 1,2,3; 1,2,0 (mod3)x v if  + =  ; ( ) 6w x  = ; 1( ) 7x w  + = ; ( ) 5u x  = ; 1( ) 4x u  + = ; 1( ) 8,9; 1,0 (mod 2)v v if  + =  For 1 2   − 1( ) 8,9; 1,0 (mod 2)x x if  + =  Based on the above procedure, the graph ( )T  is attained with 9 total colourable. Thus '' ( ( )) 9T    . Since ( ( )) 8T  = and by lemma 2.7, ''( ( )) ( ( )) 1 8 1 9T T     + = +  and Hence '' ( ( )) 9.T   = Conclusion In this paper, the total chromatic number of triple star graph and its line, middle, total , splitting graph and lobster graph are obtained, the proofs provides an optimal solution to the total chromatic number for these graphs. Overall, delving into the total chromatic number of different graph classes and exploring the determination of total coloring in allocation across various families of graphs can contribute significantly to graph theory and related fields. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 504 https://internationalpubls.com Reference [1] Akhlak Mansuri, On harmonious chromatic number of triple star graph, Journal of Hyperstructures 5 (1) (2016), 26- 32. 10.22098/JHS.2016.2651 [2] Behzad.M, Graphs and their chromatic numbers, Doctoral Thesis, Michigan State University, (1965), https://doi.org/doi:10.25335/j5he-k143 [3] Borodin O.V, On the total coloring of planar graphs, J Reine Angene math. 1989, 394:180-185. UR - http://eudml.org/doc/153105 [4] Geetha J, Narayanan. N, and Somasundaram K, Total Colorings-A Survey, AKCE International Journal of Graphs and Combinatorics, 20 (2023) 3, 339-351. https://doi.org/10.1080/09728600.2023.2187960 [5] Hamada T, Yoshimura I, Traversability and connectivity of the middle graph of a graph, [6] Discrete Mathematics, 14(1976):247–256. https://doi.org/10.1016/0012-365X(76)90037-6 [7] L.O. Harjito Dafik A I. Kristiana R. M.Prihandini, R. Alfarisi, On r-dynamic vertex coloring of line, middle, total of lobster graph, Journal of Physics: Conference series, 1465 (2020), 012014. DOI 10.1088/1742-6596/1465/1/012014 [8] Jayaraman G and D. Muthuramakrishnan, Total chromatic number of double star graph families, Journal of Adv. Research in dynamics and control systems, 10(5), 2018, PP 631-635. [9] Kostochka A.V, The total chromatic number of any multigraph with maximum degree five is atmost seven, Discrete math, 1996, 162: 199-214. https://doi.org/10.1016/0012-365X(95)00286-6 [10] Kostochka A.V, The total coloring of a multigraph with maximum degree 4, Discrete math, 1977, 17: 161-163. https://doi.org/10.1016/0012-365X(77)90146-7 [11] Kowalik L, Sereni JS, Skrekovski R, Total coloring of plane graph with maximum degree nine, SIAM J Discrete math, 2008, 22: 1462-1479. ⟨10.1137/070688389⟩⟨hal-00487320⟩ [12] Muthuramakrishnan. D and Jayaraman. G, Total Chromatic Number of Star and Bistar Graphs, International Journal of Pure and Applied Mathematics, 117 (21) 2017, 699-708. url: http://www.ijpam.eu [13] Muthuramakrishnan. D and Jayaraman. G, Total Coloring of Splitting Graph of Path, Cycle and Star Graphs International Journal of mathematics and its Applications, 6(1-D) 2018, 659-664. https://ijmaa.in/index.php/ijmaa/article/view/1124 [14] Punitha. A and Jayaraman. G, Total coloring middle graph of certain snake graph families, Journal of applied mathematics & informatics, 42(2), 2024, 353-366. https://doi.org/10.14317/jami.2024.353 [15] Punitha. A and Jayaraman. G, Computation of total chromatic number for certain convex polytope graphs, Journal of applied mathematics & informatics, 42(3), 2024,567-582. https://doi.org/10.14317/jami.2024.567 [16] Rosenfeld M, On the total coloring of certain graphs, Isreal J math, 1971, 9:396-402. https://doi.org/10.1007/BF02771690 [17] Vijayaditya N, On total chromatic number of a graph, J London Math Soc, 1971, 3:405-408. https://doi.org/10.1016/0012-365X(93)90329-R [18] Vizing V.G, Some unsolved problems in graph theory, Uspekhi Mat. Nauk(in Russian) 23(6), 117-134(in Russian) and in Russian Mathematical Survey, 23(6) (1968), 125-141. 10.1070/RM1968v023n06ABEH001252 [19] Yap, H.P. Total Colourings of Graphs. In Lecture Notes in Mathematics; Springer: Berlin, Germany, 1996; Volume 1623. https://doi.org/10.22098/jhs.2016.2651 https://doi.org/doi:10.25335/j5he-k143 http://eudml.org/doc/153105 https://doi.org/10.1080/09728600.2023.2187960 https://doi.org/10.1016/0012-365X(76)90037-6 https://doi.org/10.1016/0012-365X(95)00286-6 https://doi.org/10.1016/0012-365X(77)90146-7 https://dx.doi.org/10.1137/070688389 https://hal.science/hal-00487320 http://www.ijpam.eu/ https://ijmaa.in/index.php/ijmaa/article/view/1124 https://doi.org/10.14317/jami.2024.353 https://doi.org/10.14317/jami.2024.567 https://doi.org/10.1007/BF02771690 https://doi.org/10.1016/0012-365X(93)90329-R https://ui.adsabs.harvard.edu/link_gateway/1968RuMaS..23..125V/doi:10.1070/RM1968v023n06ABEH001252