{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T23:05:18Z","timestamp":1773615918066,"version":"3.50.1"},"reference-count":10,"publisher":"Allerton Press","issue":"7","license":[{"start":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T00:00:00Z","timestamp":1701388800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T00:00:00Z","timestamp":1701388800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Aut. Control Comp. Sci."],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.3103\/s0146411623070131","type":"journal-article","created":{"date-parts":[[2024,2,27]],"date-time":"2024-02-27T14:02:19Z","timestamp":1709042539000},"page":"760-771","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Two-Step Coloring of Grid Graphs of Different Types"],"prefix":"10.3103","volume":"57","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0980-2507","authenticated-orcid":false,"given":"A. V.","family":"Smirnov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1627","published-online":{"date-parts":[[2024,2,27]]},"reference":[{"key":"7635_CR1","doi-asserted-by":"publisher","first-page":"415","DOI":"10.3103\/s0146411616060031","volume":"50","author":"S.V. Korsakov","year":"2016","unstructured":"Korsakov, S.V., Smirnov, A.V., and Sokolov, V.A., Principles of organizing the interoperability of equipollent nodes in a wireless mesh-network with time division multiple access, Autom. Control Comput. Sci., 2016, vol. 50, no. 6, pp. 415\u2013422. https:\/\/doi.org\/10.3103\/s0146411616060031","journal-title":"Autom. Control Comput. Sci."},{"key":"7635_CR2","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"Harary, F., Graph Theory, Addison-Wesley, 1969."},{"key":"7635_CR3","doi-asserted-by":"publisher","first-page":"685","DOI":"10.3103\/s0146411620070159","volume":"54","author":"N.S. Medvedeva","year":"2020","unstructured":"Medvedeva, N.S. and Smirnov, A.V., NP-completeness and one polynomial subclass of the two-step graph coloring problem, Autom. Control Comput. Sci., 2020, vol. 54, no. 7, pp. 685\u2013696. https:\/\/doi.org\/10.3103\/s0146411620070159","journal-title":"Autom. Control Comput. Sci."},{"key":"7635_CR4","first-page":"131","volume":"11","author":"N. Medvedeva","year":"2019","unstructured":"Medvedeva, N. and Smirnov, A., Dvukhshagovaya raskraska pryamougol\u2019nogo grafa reshetki, Zametki po informatike i matematike (Notes on Informatics and Mathematics), Yaroslavl: Yaroslavl. Gos. Univ., 2019, vol. 11, pp.\u00a0131\u2013138.","journal-title":"Gos. Univ."},{"key":"7635_CR5","unstructured":"Kolmogorov, A.N., Parquets made of regular polygons, Kvant, 1970, no. 3, pp. 24\u201327."},{"key":"7635_CR6","doi-asserted-by":"publisher","unstructured":"Umans, C. and Lenhart, W., Hamiltonian cycles in solid grid graphs, Proc. 38th Annu. Symp. on Foundations of Computer Science, Miami Beach, Fla., 1997, IEEE, 1997, pp. 496\u2013505. https:\/\/doi.org\/10.1109\/sfcs.1997.646138","DOI":"10.1109\/sfcs.1997.646138"},{"key":"7635_CR7","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A. Itai","year":"1982","unstructured":"Itai, A., Papadimitriou, C.H., and Szwarcfiter, J.L., Hamilton paths in grid graphs, SIAM J. Comput., 1982, vol.\u00a011, no. 4, pp. 676\u2013686. https:\/\/doi.org\/10.1137\/0211056","journal-title":"SIAM J. Comput."},{"key":"7635_CR8","doi-asserted-by":"publisher","first-page":"6166","DOI":"10.1016\/j.disc.2007.11.040","volume":"308","author":"V.S. Gordon","year":"2007","unstructured":"Gordon, V.S., Orlovich, Yu.L., and Werner, F., Hamiltonian properties of triangular grid graphs, Discrete Math., 2007, vol. 308, no. 24, pp. 6166\u20136188. https:\/\/doi.org\/10.1016\/j.disc.2007.11.040","journal-title":"Discrete Math."},{"key":"7635_CR9","unstructured":"Islam, K., Meijer, H., N\u00fa\u00f1ez, Y., Rappaport, D., and Xiao, H., Hamilton circuits in hexagonal grid graphs, Proc. 19th Canadian Conf. on Computational Geometry (CCCG2007), Ottawa: 2007, pp. 85\u201388."},{"key":"7635_CR10","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/s11227-012-0852-0","volume":"65","author":"F. Keshavarz-Kohjerdi","year":"2013","unstructured":"Keshavarz-Kohjerdi, F. and Bagheri, A., An efficient parallel algorithm for the longest path problem in meshes, J. Supercomput., 2013, vol. 65, no. 2, pp. 723\u2013741. https:\/\/doi.org\/10.1007\/s11227-012-0852-0","journal-title":"J. Supercomput."}],"container-title":["Automatic Control and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411623070131.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.3103\/S0146411623070131","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411623070131.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T22:07:07Z","timestamp":1773612427000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.3103\/S0146411623070131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12]]},"references-count":10,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["7635"],"URL":"https:\/\/doi.org\/10.3103\/s0146411623070131","relation":{},"ISSN":["0146-4116","1558-108X"],"issn-type":[{"value":"0146-4116","type":"print"},{"value":"1558-108X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12]]},"assertion":[{"value":"18 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 February 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors of this work declare that they have no conflicts of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"CONFLICT OF INTEREST"}}]}}