{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T15:59:47Z","timestamp":1768319987907,"version":"3.49.0"},"reference-count":25,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2018,10,19]],"date-time":"2018-10-19T00:00:00Z","timestamp":1539907200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"SERB-DST","award":["(Grant SR\/S4\/MS: 867\/14)"],"award-info":[{"award-number":["(Grant SR\/S4\/MS: 867\/14)"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A total coloring of a graph G is an assignment of colors to the elements of the graph G such that no two adjacent or incident elements receive the same color. The total chromatic number of a graph G, denoted by      \u03c7  \u2033    ( G )     , is the minimum number of colors that suffice in a total coloring. Behzad and Vizing conjectured that for any graph G,     \u0394  ( G )  + 1 \u2264  \u03c7  \u2033    ( G )  \u2264 \u0394  ( G )  + 2    , where     \u0394 ( G )     is the maximum degree of G. In this paper, we prove the total coloring conjecture for certain classes of graphs of deleted lexicographic product, line graph and double graph.<\/jats:p>","DOI":"10.3390\/a11100161","type":"journal-article","created":{"date-parts":[[2018,10,19]],"date-time":"2018-10-19T10:08:02Z","timestamp":1539943682000},"page":"161","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Total Coloring Conjecture for Certain Classes of Graphs"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2454-7356","authenticated-orcid":false,"given":"R.","family":"Vignesh","sequence":"first","affiliation":[{"name":"Department of Mathematics, Amrita School of Engineering, Amrita Vishwa Vidyapeetham, Coimbatore 641112, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Geetha","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Amrita School of Engineering, Amrita Vishwa Vidyapeetham, Coimbatore 641112, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Somasundaram","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Amrita School of Engineering, Amrita Vishwa Vidyapeetham, Coimbatore 641112, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,10,19]]},"reference":[{"key":"ref_1","unstructured":"Behzad, M. (1965). Graphs and Their Chromatic Numbers. [Ph.D. Thesis, Michigan State University]."},{"key":"ref_2","unstructured":"Behzad, M. (1971). The Total Chromatic Number, Combinatorial Mathematics and Its Applications. Combinatorial Mathematics and Its Applications: Proceedings of a Conference Held at the Mathematical Institute, Oxford, 7\u201310 July 1969, Academic Press."},{"key":"ref_3","first-page":"117","article-title":"Some unsolved problems in graph theory","volume":"23","author":"Vizing","year":"1968","journal-title":"Uspekhi Mat. Nauk."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0012-365X(92)00058-Y","article-title":"Total Coloring regular bipartite graphs is NP-hard","volume":"124","author":"McDiarmid","year":"1994","journal-title":"Discret. Math."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1007\/BF01162967","article-title":"Graph Multiplication","volume":"72","author":"Sabidussi","year":"1960","journal-title":"Math. Z."},{"key":"ref_6","first-page":"30","article-title":"The Cartesian product of graphs","volume":"9","author":"Vizing","year":"1963","journal-title":"Vyc. Sis."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0893-9659(92)90010-7","article-title":"Total chromatic number","volume":"5","author":"Seoud","year":"1992","journal-title":"Appl. Math. Lett."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1080\/0020739970280402","article-title":"Total colorings of Cartesian products","volume":"28","author":"Seoud","year":"1997","journal-title":"Int. J. Math. Educ. Sci. Technol."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1016\/j.endm.2005.06.082","article-title":"The total chromatic number of some bipartite graphs","volume":"22","author":"Campos","year":"2005","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1016\/j.dam.2008.08.030","article-title":"Equitable total coloring of Cn\u2610Cm","volume":"157","author":"Tong","year":"2009","journal-title":"Discret. Appl. Math."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/s12190-009-0296-8","article-title":"On total chromatic number of direct product graphs","volume":"33","author":"Pranavar","year":"2010","journal-title":"J. Appl. Math. Comput."},{"key":"ref_12","first-page":"58","article-title":"Total coloring of generalized sierpi\u0144ski graphs","volume":"63","author":"Geetha","year":"2015","journal-title":"Aust. J. Comb."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"223","DOI":"10.2478\/v10209-011-0012-y","article-title":"A survey of graph coloring\u2014Its types, methods and applications","volume":"37","author":"Formanowicz","year":"2012","journal-title":"Found. Comput. Decis. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/s00373-018-1876-x","article-title":"Total Colorings of Product Graphs","volume":"34","author":"Geetha","year":"2018","journal-title":"Graphs Comb."},{"key":"ref_15","first-page":"15","article-title":"Total coloring of the corona product of two graphs","volume":"68","author":"Mohan","year":"2017","journal-title":"Aust. J. Comb."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.endm.2016.05.016","article-title":"Total Coloring of Certain Classes of Product Graphs","volume":"53","author":"Mohan","year":"2016","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Yap, H.P. (1996). Total Colourings of Graphs. Lecture Notes in Mathematics, Springer.","DOI":"10.1007\/BFb0092895"},{"key":"ref_18","unstructured":"Imrich, W., and Klav\u017ear, S. (2000). Product Graphs: Structure and Recognition, Wiley."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1016\/j.dam.2011.03.011","article-title":"Equistable graphs, general partition graphs, triangle graphs, and graph products","volume":"159","year":"2011","journal-title":"Discr. Appl. Math."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"26","DOI":"10.37236\/475","article-title":"Rainbow Matching in Edge-Colored Graphs","volume":"17","author":"LeSaulnier","year":"2010","journal-title":"Electron. J. Comb."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0012-365X(96)00045-3","article-title":"Claw-free graphs\u2014A survey","volume":"164","author":"Faudree","year":"1997","journal-title":"Discret. Math."},{"key":"ref_22","unstructured":"Sachs, H., Voss, H., and Walther, H. (1968). Derived graphs and digraphs. Beitra\u00a8ge zur Graphentheorie, Teubner."},{"key":"ref_23","first-page":"109","article-title":"Vertex Distinguishing Edge- and Total-Colorings of Cartesian and other Product Graphs","volume":"107","author":"Baril","year":"2012","journal-title":"Ars Comb."},{"key":"ref_24","first-page":"99","article-title":"Total Colorings of Cartesian Products of Graphs","volume":"165","author":"Kemnitz","year":"2003","journal-title":"Congr. Numer."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1016\/j.disc.2006.11.038","article-title":"Double graphs","volume":"308","author":"Munarini","year":"2008","journal-title":"Discret. Math."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/10\/161\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:26:47Z","timestamp":1760196407000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/10\/161"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,19]]},"references-count":25,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2018,10]]}},"alternative-id":["a11100161"],"URL":"https:\/\/doi.org\/10.3390\/a11100161","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,19]]}}}