{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:36:52Z","timestamp":1774370212298,"version":"3.50.1"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,9,27]],"date-time":"2011-09-27T00:00:00Z","timestamp":1317081600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2011,9,27]],"date-time":"2011-09-27T00:00:00Z","timestamp":1317081600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Braz Comput Soc"],"published-print":{"date-parts":[[2011,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The class of unichord-free graphs was recently investigated in a series of papers (Machado et al. in Theor. Comput. Sci. 411:1221\u20131234, 2010; Machado, de Figueiredo in Discrete Appl. Math. 159:1851\u20131864, 2011; Trotignon, Vu\u0161kovi\u0107 in J. Graph Theory 63:31\u201367, 2010) and proved to be useful with respect to the study of the complexity of colouring problems. In particular, several surprising complexity dichotomies could be found in subclasses of unichord-free graphs. We discuss such results based on the concept of \u201cseparating class\u201d and we describe the class of bipartite unichord-free as a final missing separating class with respect to edge-colouring and total-colouring problems, by proving that total-colouring bipartite unichord-free graphs is NP-complete.<\/jats:p>","DOI":"10.1007\/s13173-011-0040-8","type":"journal-article","created":{"date-parts":[[2011,9,26]],"date-time":"2011-09-26T10:26:23Z","timestamp":1317032783000},"page":"281-285","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Complexity separating classes for edge-colouring and total-colouring"],"prefix":"10.1007","volume":"17","author":[{"given":"Raphael","family":"Machado","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Celina","family":"de Figueiredo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,9,27]]},"reference":[{"key":"40_CR1","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1006\/jctb.1997.1780","volume":"71","author":"O Borodin","year":"1997","unstructured":"Borodin O, Kostochka A, Woodall D (1997) List edge and list total colourings of multigraphs. J Comb Theory, Ser A 71:184\u2013204","journal-title":"J Comb Theory, Ser A"},{"key":"40_CR2","first-page":"335","volume":"88","author":"C Campos","year":"2008","unstructured":"Campos C, Mello C (2008) The total chromatic number of some bipartite graphs. Ars Comb 88:335\u2013347","journal-title":"Ars Comb"},{"key":"40_CR3","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D Johnson","year":"1985","unstructured":"Johnson D (1985) The NP-completeness column: an ongoing guide. J Algorithms 6:434\u2013451","journal-title":"J Algorithms"},{"key":"40_CR4","first-page":"104","volume":"34","author":"D K\u00f6nig","year":"1916","unstructured":"K\u00f6nig D (1916) Graphok \u00e9s alkalmaz\u00e1suk a determin\u00e1nsok \u00e9s a halmazok elm\u00e9let\u00e9re. Math Termtud Ertesito 34:104\u2013119","journal-title":"Math Termtud Ertesito"},{"key":"40_CR5","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","volume":"4","author":"D Leven","year":"1983","unstructured":"Leven D, Galil Z (1983) NP-completeness of finding the chromatic index of regular graphs. J Algorithms 4:35\u201344","journal-title":"J Algorithms"},{"key":"40_CR6","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/j.endm.2010.05.085","volume":"36","author":"R Machado","year":"2010","unstructured":"Machado R, de Figueiredo C (2010) Total chromatic number of {square,unichord}-free graphs. Electron Notes Discrete Math 36:671\u2013678","journal-title":"Electron Notes Discrete Math"},{"key":"40_CR7","doi-asserted-by":"publisher","first-page":"1851","DOI":"10.1016\/j.dam.2011.03.024","volume":"159","author":"R Machado","year":"2011","unstructured":"Machado R, de Figueiredo C (2011) Total chromatic number of unichord-free graphs. Discrete Appl Math 159:1851\u20131864","journal-title":"Discrete Appl Math"},{"key":"40_CR8","doi-asserted-by":"publisher","first-page":"1221","DOI":"10.1016\/j.tcs.2009.12.018","volume":"411","author":"R Machado","year":"2010","unstructured":"Machado R, de Figueiredo C, Vu\u0161kovi\u0107 K (2010) Chromatic index of graphs with no cycle with unique chord. Theor Comput Sci 411:1221\u20131234","journal-title":"Theor Comput Sci"},{"key":"40_CR9","unstructured":"Machado R, de Figueiredo C, Trotignon N Edge-colouring and total-colouring chordless graphs. Manuscript available at http:\/\/www.liafa.jussieu.fr\/~trot\/articles\/chordless.pdf"},{"key":"40_CR10","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0012-365X(92)00058-Y","volume":"124","author":"C McDiarmid","year":"1994","unstructured":"McDiarmid C, S\u00e1nchez-Arroyo A (1994) Total colouring regular bipartite graphs is NP-hard. Discrete Math 124:155\u2013162","journal-title":"Discrete Math"},{"key":"40_CR11","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1002\/jgt.20405","volume":"63","author":"N Trotignon","year":"2010","unstructured":"Trotignon N, Vu\u0161kovi\u0107 K (2010) A structure theorem for graphs with no cycle with a unique chord and its consequences. J Graph Theory 63:31\u201367","journal-title":"J Graph Theory"},{"key":"40_CR12","series-title":"Lecture notes in mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0092895","volume-title":"Total colourings of graphs","author":"HP Yap","year":"1996","unstructured":"Yap HP (1996) Total colourings of graphs. Lecture notes in mathematics, vol 1623. Springer, Berlin"}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-011-0040-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13173-011-0040-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-011-0040-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-011-0040-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T15:56:12Z","timestamp":1630511772000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1007\/s13173-011-0040-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,27]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["40"],"URL":"https:\/\/doi.org\/10.1007\/s13173-011-0040-8","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"value":"0104-6500","type":"print"},{"value":"1678-4804","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9,27]]},"assertion":[{"value":"14 May 2011","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2011","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2011","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}