{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T13:38:56Z","timestamp":1746625136265,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T00:00:00Z","timestamp":1722988800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T00:00:00Z","timestamp":1722988800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider two different notions of graph colouring, namely, the <jats:italic>t<\/jats:italic>-periodic colouring for vertices that has been introduced in 1974 by Bondy and Simonovits, and the periodic colouring for oriented edges that has been recently introduced in the context of spectral theory of non-backtracking operators. For each of these two colourings, we introduce the corresponding colouring number which is given by maximising the possible number of colours. We first investigate these two new colouring numbers individually, and we then show that there is a deep relationship between them.<\/jats:p>","DOI":"10.1007\/s00373-024-02823-3","type":"journal-article","created":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T09:02:16Z","timestamp":1723021336000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Maximal Colourings for Graphs"],"prefix":"10.1007","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4995-6479","authenticated-orcid":false,"given":"Raffaella","family":"Mulas","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,7]]},"reference":[{"issue":"4","key":"2823_CR1","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1038\/scientificamerican1077-108","volume":"237","author":"K Appel","year":"1977","unstructured":"Appel, K., Haken, W.: The solution of the four-color-map problem. Sci. Am. 237(4), 108\u2013121 (1977)","journal-title":"Sci. Am."},{"key":"2823_CR2","first-page":"1","volume":"476","author":"F Arrigo","year":"2020","unstructured":"Arrigo, F., Higham, D., Noferini, V.: Beyond non-backtracking: non-cycling network centrality measures. Proc. Math. Phys. Eng. Scie. 476, 1 (2020)","journal-title":"Proc. Math. Phys. Eng. Scie."},{"key":"2823_CR3","unstructured":"Arrigo, F., Higham, D., Noferini, V., Wood, R.: Weighted enumeration of nonbacktracking walks on weighted graphs. Preprint arXiv:2202.02888 (2022)"},{"issue":"3","key":"2823_CR4","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1002\/rsa.20562","volume":"47","author":"\u00c1 Backhausz","year":"2015","unstructured":"Backhausz, \u00c1., Szegedy, B., Vir\u00e1g, B.: Ramanujan graphings and correlation decay in local algorithms. Rand. Struct. Algorithms 47(3), 424\u2013435 (2015)","journal-title":"Rand. Struct. Algorithms"},{"issue":"06","key":"2823_CR5","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1142\/S0129167X92000357","volume":"3","author":"H Bass","year":"1992","unstructured":"Bass, H.: The Ihara\u2013Selberg zeta function of a tree lattice. Int. J. Math. 3(06), 717\u2013797 (1992)","journal-title":"Int. J. Math."},{"issue":"2","key":"2823_CR6","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0095-8956(74)90052-5","volume":"16","author":"JA Bondy","year":"1974","unstructured":"Bondy, J.A., Simonovits, M.: Cycles of even length in graphs. J. Comb. Theory Ser. B 16(2), 97\u2013105 (1974)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"2823_CR7","first-page":"1","volume":"46","author":"C Bordenave","year":"2018","unstructured":"Bordenave, C., Lelarge, M., Massouli\u00e9, L.: Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs. Ann. Prob. Off. J. Inst. Math. Stat. 46(1), 1\u201371 (2018)","journal-title":"Ann. Prob. Off. J. Inst. Math. Stat."},{"issue":"5","key":"2823_CR8","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.98.052313","volume":"98","author":"C Castellano","year":"2018","unstructured":"Castellano, C., Pastor-Satorras, R.: Relevance of backtracking paths in recurrent-state epidemic spreading on networks. Phys. Rev. E 98(5), 052313 (2018)","journal-title":"Phys. Rev. E"},{"issue":"1","key":"2823_CR9","doi-asserted-by":"publisher","first-page":"R84","DOI":"10.37236\/173","volume":"16","author":"Y Cooper","year":"2009","unstructured":"Cooper, Y.: Properties determined by the Ihara zeta function of a graph. Electron. J. Comb. 16(1), R84 (2009)","journal-title":"Electron. J. Comb."},{"issue":"03","key":"2823_CR10","doi-asserted-by":"publisher","first-page":"2150028","DOI":"10.1142\/S2010326321500283","volume":"10","author":"S Coste","year":"2021","unstructured":"Coste, S., Zhu, Y.: Eigenvalues of the non-backtracking operator detached from the bulk. Rand. Mat. Theory Appl. 10(03), 2150028 (2021)","journal-title":"Rand. Mat. Theory Appl."},{"key":"2823_CR11","unstructured":"Csikvari, P.: Discrete Mathematics. Lecture Note (2023). http:\/\/csikvarip.web.elte.hu\/discrete_mathematics_lecture_notes.pdf"},{"key":"2823_CR12","unstructured":"Euler, L.: Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae 8(1741), 128\u2013140 (1736)"},{"key":"2823_CR13","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.laa.2021.01.022","volume":"618","author":"C Glover","year":"2021","unstructured":"Glover, C., Kempton, M.: Some spectral properties of the non-backtracking matrix of a graph. Linear Algebra Appl. 618, 37\u201357 (2021)","journal-title":"Linear Algebra Appl."},{"key":"2823_CR14","volume-title":"Erd\u0151s\u2013Ko\u2013Rado Theorems: Algebraic Approaches, Cambridge Studies in Advanced Mathematics","author":"C Godsil","year":"2016","unstructured":"Godsil, C., Meagher, K.: Erd\u0151s\u2013Ko\u2013Rado Theorems: Algebraic Approaches, Cambridge Studies in Advanced Mathematics, vol. 149. Cambridge University Press, Cambridge (2016)"},{"issue":"1","key":"2823_CR15","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/17M1112297","volume":"39","author":"P Grindrod","year":"2018","unstructured":"Grindrod, P., Higham, D., Noferini, V.: The deformed graph Laplacian and its applications to network centrality analysis. SIAM J. Matrix Anal. Appl. 39(1), 310\u2013341 (2018). https:\/\/doi.org\/10.1137\/17M1112297","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"2823_CR16","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1017\/S0370164600044631","volume":"10","author":"F Guthrie","year":"1880","unstructured":"Guthrie, F.: Note on the colouring of maps. Proc. R. Soc. Edinb. 10, 727\u2013728 (1880)","journal-title":"Proc. R. Soc. Edinb."},{"key":"2823_CR17","doi-asserted-by":"crossref","unstructured":"Hashimoto, K.: Zeta functions of finite graphs and representations of $$p$$-adic groups. In: Automorphic Forms and Geometry of Arithmetic Varieties, Advanced Studies in Pure Mathematics, vol.\u00a015, pp. 211\u2013280. Elsevier, London (1989)","DOI":"10.1016\/B978-0-12-330580-0.50015-X"},{"issue":"3","key":"2823_CR18","doi-asserted-by":"publisher","first-page":"949","DOI":"10.4007\/annals.2019.190.3.6","volume":"190","author":"H Huang","year":"2019","unstructured":"Huang, H.: Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Ann. Math. (2) 190(3), 949\u2013955 (2019)","journal-title":"Ann. Math. (2)"},{"key":"2823_CR19","volume-title":"Graph Coloring Problems","author":"TR Jensen","year":"2011","unstructured":"Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley, London (2011)"},{"issue":"10","key":"2823_CR20","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2023.113536","volume":"346","author":"J Jost","year":"2023","unstructured":"Jost, J., Mulas, R., Torres, L.: Spectral theory of the non-backtracking Laplacian for graphs. Discrete Math. 346(10), 113536 (2023)","journal-title":"Discrete Math."},{"issue":"52","key":"2823_CR21","doi-asserted-by":"publisher","first-page":"20935","DOI":"10.1073\/pnas.1312486110","volume":"110","author":"F Krzakala","year":"2013","unstructured":"Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborov\u00e1, L., Zhang, P.: Spectral redemption in clustering sparse networks. Proc. Natl. Acad. Sci. 110(52), 20935\u201320940 (2013)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"2823_CR22","first-page":"104","volume":"34","author":"D Konig","year":"1916","unstructured":"Konig, D.: Graphok \u00e9s alkalmaz\u00e1suk a determin\u00e1nsok \u00e9s a halmazok elm\u00e9let\u00e9re. Math. Term\u00e9szettudom\u00e1nyi Ertesito 34, 104\u2013119 (1916)","journal-title":"Math. Term\u00e9szettudom\u00e1nyi Ertesito"},{"key":"2823_CR23","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s00283-012-9307-y","volume":"34","author":"P Maritz","year":"2012","unstructured":"Maritz, P., Mouton, S.: Francis Guthrie: a colourful life. Math. Intell. 34, 67\u201375 (2012)","journal-title":"Math. Intell."},{"issue":"5","key":"2823_CR24","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.90.052808","volume":"90","author":"T Martin","year":"2014","unstructured":"Martin, T., Zhang, X., Newman, M.: Localization and centrality in networks. Phys. Rev. E 90(5), 052808 (2014)","journal-title":"Phys. Rev. E"},{"key":"2823_CR25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.99.052309","volume":"99","author":"A Mellor","year":"2019","unstructured":"Mellor, A., Grusovin, A.: Graph comparison via the nonbacktracking spectrum. Phys. Rev. E 99, 052309 (2019). https:\/\/doi.org\/10.1103\/PhysRevE.99.052309","journal-title":"Phys. Rev. E"},{"key":"2823_CR26","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/j.laa.2023.10.014","volume":"680","author":"R Mulas","year":"2024","unstructured":"Mulas, R., Zhang, D., Zucal, G.: There is no going back: properties of the non-backtracking Laplacian. Linear Algebra Appl. 680, 341\u2013370 (2024)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"2823_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41598-020-78582-x","volume":"10","author":"R Pastor-Satorras","year":"2020","unstructured":"Pastor-Satorras, R., Castellano, C.: The localization of non-backtracking centrality in networks and its physical consequences. Sci. Rep. 10(1), 1\u201312 (2020)","journal-title":"Sci. Rep."},{"issue":"2","key":"2823_CR28","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.92.022821","volume":"92","author":"M Shrestha","year":"2015","unstructured":"Shrestha, M., Scarpino, S., Moore, C.: Message-passing approach for recurrent-state epidemic models on networks. Phys. Rev. E 92(2), 022821 (2015)","journal-title":"Phys. Rev. E"},{"key":"2823_CR29","doi-asserted-by":"crossref","unstructured":"Terras, A.: Zeta functions of graphs: a stroll through the garden. In: Cambridge Studies in Advanced Mathematics, vol. 128. Cambridge University Press, Cambridge (2010)","DOI":"10.1017\/CBO9780511760426"},{"key":"2823_CR30","unstructured":"Torres, L.: Non-backtracking spectrum: unitary eigenvalues and diagonalizability. Preprint arXiv:2007.13611 (2020)"},{"key":"2823_CR31","unstructured":"Torres, L., Chan, K., Tong, H., Eliassi-Rad, T.: Node immunization with non-backtracking eigenvalues. Preprint arXiv:2002.12309 (2020)"},{"issue":"2","key":"2823_CR32","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/20M1352132","volume":"3","author":"L Torres","year":"2021","unstructured":"Torres, L., Chan, K., Tong, H., Eliassi-Rad, T.: Nonbacktracking eigenvalues under node removal: X-centrality and targeted immunization. SIAM J. Math. Data Sci. 3(2), 656\u2013675 (2021)","journal-title":"SIAM J. Math. Data Sci."},{"issue":"1","key":"2823_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s41109-019-0147-y","volume":"4","author":"L Torres","year":"2019","unstructured":"Torres, L., Su\u00e1rez-Serrato, P., Eliassi-Rad, T.: Non-backtracking cycles: length spectrum theory and graph mining applications. Appl. Netw. Sci. 4(1), 1\u201335 (2019)","journal-title":"Appl. Netw. Sci."},{"key":"2823_CR34","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/BF03023063","volume":"1","author":"WT Tutte","year":"1978","unstructured":"Tutte, W.T.: Colouring problems. Math. Intell. 1, 72\u201375 (1978)","journal-title":"Math. Intell."},{"key":"2823_CR35","first-page":"25","volume":"3","author":"VG Vizing","year":"1964","unstructured":"Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Diskret. Anal. 3, 25\u201330 (1964)","journal-title":"Diskret. Anal."},{"key":"2823_CR36","unstructured":"Voloshin, V.I.: Graph coloring: history, results and open problems. Alabama Journal of Mathematics, Spring\/Fall (2009)"},{"key":"2823_CR37","volume-title":"Four Colors Suffice: How the Map Problem Was Solved-Revised","author":"R Wilson","year":"2013","unstructured":"Wilson, R.: Four Colors Suffice: How the Map Problem Was Solved-Revised, Color Princeton University Press, Princeton (2013)","edition":"Color"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02823-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-024-02823-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02823-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,24]],"date-time":"2024-10-24T15:04:08Z","timestamp":1729782248000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-024-02823-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,7]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["2823"],"URL":"https:\/\/doi.org\/10.1007\/s00373-024-02823-3","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2024,8,7]]},"assertion":[{"value":"30 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 July 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"93"}}