{"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":1740144483741,"version":"3.37.3"},"reference-count":19,"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\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002923","name":"CONICET","doi-asserted-by":"crossref","award":["PIP 11220200100084CO"],"award-info":[{"award-number":["PIP 11220200100084CO"]}],"id":[{"id":"10.13039\/501100002923","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003074","name":"ANPCyT","doi-asserted-by":"crossref","award":["PICT-2021-I-A-00755"],"award-info":[{"award-number":["PICT-2021-I-A-00755"]}],"id":[{"id":"10.13039\/501100003074","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100010253","name":"UBACyT","doi-asserted-by":"crossref","award":["20020170100495BA"],"award-info":[{"award-number":["20020170100495BA"]}],"id":[{"id":"10.13039\/501100010253","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100010253","name":"UBACyT","doi-asserted-by":"crossref","award":["20020160100095BA"],"award-info":[{"award-number":["20020160100095BA"]}],"id":[{"id":"10.13039\/501100010253","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,2,2]]},"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:p>Interval graphs and proper interval graphs are well known graph classes, for which several generalizations have been proposed in the literature. In this work, we study the (proper) thinness, and several variations, for the classes of cographs, crowns graphs and grid graphs. We provide the exact values for several variants of thinness (proper, independent, complete, precedence, and combinations of them) for the crown graphs CR<jats:italic><jats:sub>n<\/jats:sub><\/jats:italic>. For cographs, we prove that the precedence thinness can be determined in polynomial time. We also improve known bounds for the thinness of <jats:italic>n<\/jats:italic> \u00d7 <jats:italic>n<\/jats:italic> grids GR<jats:italic><jats:sub>n<\/jats:sub><\/jats:italic> and <jats:italic>m\u00d7n<\/jats:italic> grids GR<jats:sub><jats:italic>m,n<\/jats:italic><\/jats:sub>, proving that <jats:italic>n<\/jats:italic>\u22121\/3 \u2264 thin(GR<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>) \u2264 <jats:italic>n<\/jats:italic>+1\/2. Regarding the precedence thinness, we prove that prec-thin(GR<jats:sub><jats:italic>n<\/jats:italic>,2<\/jats:sub>) = <jats:italic>n<\/jats:italic>+1\/2 and that <jats:italic>n<\/jats:italic>\u2212 1 + 3\/2 \u2264 prec-thin(GR<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>) \u2264 <jats:italic>n<\/jats:italic>\u2212 1 2. As applications, we show that the <jats:italic>k<\/jats:italic>-coloring problem is NP-complete for precedence 2-thin graphs and for proper 2-thin graphs, when <jats:italic>k<\/jats:italic> is part of the input. On the positive side, it is polynomially solvable for precedence proper 2-thin graphs, given the order and partition.<\/jats:p>","DOI":"10.1051\/ro\/2024033","type":"journal-article","created":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T09:05:16Z","timestamp":1707210316000},"page":"1681-1702","source":"Crossref","is-referenced-by-count":0,"title":["Thinness and its variations on some graph families and coloring graphs of bounded thinness"],"prefix":"10.1051","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9872-7528","authenticated-orcid":false,"given":"Flavia","family":"Bonomo-Braberman","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0003-2559-7173","authenticated-orcid":false,"given":"Eric","family":"Brandwein","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8498-2472","authenticated-orcid":false,"given":"Fabiano S.","family":"Oliveira","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2638-0753","authenticated-orcid":false,"suffix":"Jr.","given":"Moyses S.","family":"Sampaio","sequence":"additional","affiliation":[]},{"given":"Agustin","family":"Sansone","sequence":"additional","affiliation":[]},{"given":"Jayme L.","family":"Szwarcfiter","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2024,4,12]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/j.dam.2018.03.072","volume":"261","author":"Bonomo","year":"2019","journal-title":"Discrete Appl. Math."},{"key":"R2","doi-asserted-by":"crossref","first-page":"6261","DOI":"10.1016\/j.tcs.2011.07.012","volume":"412","author":"Bonomo","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"R3","doi-asserted-by":"crossref","first-page":"2027","DOI":"10.1016\/j.disc.2012.03.019","volume":"312","author":"Bonomo","year":"2012","journal-title":"Discrete Math."},{"key":"R4","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.dam.2023.06.013","volume":"339","author":"Bonomo-Braberman","year":"2023","journal-title":"Discrete Appl. Math."},{"key":"R5","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/j.dam.2021.04.003","volume":"312","author":"Bonomo-Braberman","year":"2022","journal-title":"Discrete Appl. Math."},{"key":"R6","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/j.dam.2021.05.020","volume":"323","author":"Bonomo-Braberman","year":"2022","journal-title":"Discrete Appl. Math."},{"key":"R7","doi-asserted-by":"crossref","first-page":"103493","DOI":"10.1016\/j.jcss.2023.103493","volume":"140","author":"Bonomo-Braberman","year":"2024","journal-title":"J. Comput. Syst. Sci"},{"key":"R8","first-page":"335","volume":"13","author":"Booth","year":"1976","journal-title":"J. Comput. Sci. Technol."},{"key":"R9","unstructured":"Brandwein E. and Sansone A., On the thinness of trees and other graph classes. Master\u2019s thesis, Departament of Computer Science, FCEyN, University of Buenos Aires, Buenos Aires (2022)."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Chandran S., Mannino C. and Oriolo G., The indepedent set problem and the thinness of a graph. Manuscript (2007).","DOI":"10.1016\/j.orl.2006.01.009"},{"key":"R11","doi-asserted-by":"crossref","first-page":"3281","DOI":"10.1007\/s00453-021-00846-3","volume":"83","author":"Chaplick","year":"2021","journal-title":"Algorithmica"},{"key":"R12","first-page":"63","volume":"21","author":"Chv\u00e1tal","year":"1984","journal-title":"Ann. Discrete Math."},{"key":"R13","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"Corneil","year":"1981","journal-title":"Discrete Appl. Math."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Golumbic M., Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980).","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"R15","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1016\/j.dam.2009.02.007","volume":"158","author":"Jel\u00ednek","year":"2010","journal-title":"Discrete Appl. Math."},{"key":"R16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.orl.2006.01.009","volume":"35","author":"Mannino","year":"2007","journal-title":"Oper. Res. Lett."},{"key":"R17","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0020-0190(91)90245-D","volume":"37","author":"Olariu","year":"1991","journal-title":"Inf. Process. Lett."},{"key":"R18","unstructured":"Roberts F., On the boxicity and cubicity of a graph, in Recent Progress in Combinatorics, edited by Tutte W.. Academic Press (1969) 301\u2013310."},{"key":"R19","unstructured":"Vatshelle M., New width parameters of graphs. Ph.D. thesis, Department of Informatics, University of Bergen (2012)."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024033\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,12]],"date-time":"2024-04-12T08:27:43Z","timestamp":1712910463000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024033"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3]]},"references-count":19,"journal-issue":{"issue":"2"},"alternative-id":["ro230168"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024033","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,3]]}}}