{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:03Z","timestamp":1740144483701,"version":"3.37.3"},"reference-count":14,"publisher":"EDP Sciences","issue":"2","license":[{"start":{"date-parts":[[2024,4,12]],"date-time":"2024-04-12T00:00:00Z","timestamp":1712880000000},"content-version":"vor","delay-in-days":42,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["302823\/2016-6, 407635\/2018-1 and 313797\/2020-0"],"award-info":[{"award-number":["302823\/2016-6, 407635\/2018-1 and 313797\/2020-0"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004586","name":"FAPERJ","doi-asserted-by":"crossref","award":["E-26\/202.793\/2017, E-26\/010.002674\/2019 and E-26\/211.666\/2021"],"award-info":[{"award-number":["E-26\/202.793\/2017, E-26\/010.002674\/2019 and E-26\/211.666\/2021"]}],"id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,2,15]]},"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:p>A<jats:italic>k-total coloring<\/jats:italic>of a graph<jats:italic>G<\/jats:italic>is an assignment of<jats:italic>k<\/jats:italic>colors to the elements (vertices and edges) of<jats:italic>G<\/jats:italic>so that adjacent or incident elements have different colors. The total chromatic number is the smallest integer<jats:italic>k<\/jats:italic>for which<jats:italic>G<\/jats:italic>has a<jats:italic>k<\/jats:italic>-total coloring. The well known Total Coloring Conjecture states that the total chromatic number of a graph is either \u0394(<jats:italic>G<\/jats:italic>) + 1 (called Type 1) or \u0394(<jats:italic>G<\/jats:italic>) + 2 (called Type 2), where \u0394(<jats:italic>G<\/jats:italic>) is the maximum degree of<jats:italic>G<\/jats:italic>. We consider the direct product of complete graphs<jats:italic>K<jats:sub>m<\/jats:sub><\/jats:italic>\u00d7<jats:italic>K<jats:sub>n<\/jats:sub><\/jats:italic>. It is known that if at least one of the numbers<jats:italic>m<\/jats:italic>or<jats:italic>n<\/jats:italic>is even, then<jats:italic>K<jats:sub>m<\/jats:sub><\/jats:italic>\u00d7<jats:italic>K<jats:sub>n<\/jats:sub><\/jats:italic>is Type 1, except for<jats:italic>K<\/jats:italic><jats:sub>2<\/jats:sub>\u00d7<jats:italic>K<\/jats:italic><jats:sub>2<\/jats:sub>. We prove that the graph<jats:italic>K<jats:sub>m<\/jats:sub><\/jats:italic>\u00d7<jats:italic>K<jats:sub>n<\/jats:sub><\/jats:italic>is Type 1 when both<jats:italic>m<\/jats:italic>and<jats:italic>n<\/jats:italic>are odd numbers, by using that the conformable condition is sufficient for the graph<jats:italic>K<jats:sub>m<\/jats:sub><\/jats:italic>\u00d7<jats:italic>K<jats:sub>n<\/jats:sub><\/jats:italic>to be Type 1 when both<jats:italic>m<\/jats:italic>and<jats:italic>n<\/jats:italic>are large enough, and by constructing the target total colorings by using Hamiltonian decompositions and a specific color class, called guiding color. We additionally apply our technique to the direct product<jats:italic>C<jats:sub>m<\/jats:sub><\/jats:italic>\u00d7<jats:italic>K<jats:sub>n<\/jats:sub><\/jats:italic>of a cycle with a complete graph. Interestingly, we are able to find a Type 2 infinite family<jats:italic>C<jats:sub>m<\/jats:sub><\/jats:italic>\u00d7<jats:italic>K<jats:sub>n<\/jats:sub><\/jats:italic>, when<jats:italic>m<\/jats:italic>is not a multiple of 3 and<jats:italic>n<\/jats:italic>= 2. We provide evidence to conjecture that all other<jats:italic>C<jats:sub>m<\/jats:sub><\/jats:italic>\u00d7<jats:italic>K<jats:sub>n<\/jats:sub><\/jats:italic>are Type 1.<\/jats:p>","DOI":"10.1051\/ro\/2024045","type":"journal-article","created":{"date-parts":[[2024,2,16]],"date-time":"2024-02-16T19:56:10Z","timestamp":1708113370000},"page":"1609-1632","source":"Crossref","is-referenced-by-count":0,"title":["On the total chromatic number of the direct product of cycles and complete graphs"],"prefix":"10.1051","volume":"58","author":[{"given":"Diane","family":"Castonguay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Celina M.H.","family":"de Figueiredo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luis A.B.","family":"Kowada","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Caroline S.R.","family":"Patr\u00e3o","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diana","family":"Sasaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mario","family":"Valencia-Pabon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2024,4,12]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Alspach B., Bermond J.-C. and Sotteau D., Decomposition Into Cycles I: Hamilton decompositions, in Proceedings of the NATO Advanced Research Workshop on Cycles and Rays: Basic Structures in Finite and Infinite Graphs held in Montreal, Quebec, May 3\u20139, 1987, edited by Hahn G., Sabidussi G. and Woodrow R.E.. Kluwer, Dordrecht, Holland (1990).","DOI":"10.1007\/978-94-009-0517-7_2"},{"key":"R2","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1112\/jlms\/s1-42.1.226","volume":"42","author":"Behzad","year":"1967","journal-title":"J. London Math. Soc."},{"key":"R3","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/j.procs.2021.11.038","volume":"195","author":"Castonguay","year":"2021","journal-title":"Proc. Comput. Sci."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Castonguay D., de Figueiredo C.M.H., Kowada L.A.B., Patr\u00e3o C.S.R. and Sasaki D., On total coloring the direct product of cycles and bipartite direct product of graphs. Discrete Math. (2023). DOI: 10.1016\/j.disc.2023.113340.","DOI":"10.1016\/j.disc.2023.113340"},{"key":"R5","first-page":"195","volume":"66","author":"Chetwynd","year":"1988","journal-title":"Congr. Numer."},{"key":"R6","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1112\/jlms\/s2-44.2.193","volume":"44","author":"Chetwynd","year":"1991","journal-title":"J. London Math. Soc."},{"key":"R7","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0012-365X(95)00034-T","volume":"154","author":"Chew","year":"1996","journal-title":"Discrete Math."},{"key":"R8","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/s00373-018-1876-x","volume":"34","author":"Geetha","year":"2018","journal-title":"Graphs Combin."},{"key":"R9","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0012-365X(93)90329-R","volume":"117","author":"Hilton","year":"1993","journal-title":"Discrete Math."},{"key":"R10","doi-asserted-by":"crossref","first-page":"67","DOI":"10.55016\/ojs\/cdm.v15i1.62679","volume":"15","author":"Janssen","year":"2020","journal-title":"Contrib. Discrete Math."},{"key":"R11","first-page":"723","volume":"23","author":"Jha","year":"1992","journal-title":"Indian J. Pure Appl. Math."},{"key":"R12","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/BF02771690","volume":"9","author":"Rosenfeld","year":"1971","journal-title":"Israel J. Math."},{"key":"R13","first-page":"25","volume":"3","author":"Vizing","year":"1964","journal-title":"Metody Diskret. Anal."},{"key":"R14","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0012-365X(94)00291-P","volume":"140","author":"Yap","year":"1995","journal-title":"Discrete Math."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024045\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T18:16:49Z","timestamp":1731349009000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3]]},"references-count":14,"journal-issue":{"issue":"2"},"alternative-id":["ro230047"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024045","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,3]]}}}