{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T12:48:31Z","timestamp":1772714911595,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,8,1]],"date-time":"2015-08-01T00:00:00Z","timestamp":1438387200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1007\/s10878-015-9941-3","type":"journal-article","created":{"date-parts":[[2015,7,31]],"date-time":"2015-07-31T07:19:00Z","timestamp":1438327140000},"page":"147-155","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A linear-time algorithm for clique-coloring problem in circular-arc graphs"],"prefix":"10.1007","volume":"33","author":[{"given":"Zuosong","family":"Liang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erfang","family":"Shan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuzhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,1]]},"reference":[{"key":"9941_CR1","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0012-365X(91)90055-7","volume":"88","author":"T Andreae","year":"1991","unstructured":"Andreae T, Schughart M, Zs Tuza (1991) Clique-transversal sets of line graphs and complements of line graphs. Discrete Math 88:11\u201320","journal-title":"Discrete Math"},{"key":"9941_CR2","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1137\/S0895480199359995","volume":"17","author":"G Bacs\u00f3","year":"2004","unstructured":"Bacs\u00f3 G, Gravier S, Gy\u00e1rf\u00e1s A, Preissmann M, Seb\u0151 A (2004) Coloring the maximal cliques of graphs. SIAM J Discrete Math 17:361\u2013376","journal-title":"SIAM J Discrete Math"},{"key":"9941_CR3","first-page":"15","volume":"11","author":"G Bacs\u00f3","year":"2009","unstructured":"Bacs\u00f3 G, Zs Tuza (2009) Clique-transversal sets and weak 2-colorings in graphs of small maximum degree. Discrete Math Theor Comput Sci 11:15\u201324","journal-title":"Discrete Math Theor Comput Sci"},{"key":"9941_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph theory","author":"JA Bondy","year":"2008","unstructured":"Bondy JA, Murty USR (2008) Graph theory. Springer, New York"},{"key":"9941_CR5","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF03322499","volume":"7","author":"PL Butzer","year":"1984","unstructured":"Butzer PL, Nessel RJ, Stark EL (1984) Eduard Helly (1884\u20131943): in memoriam. Result Math 7:145\u2013153","journal-title":"Result Math"},{"key":"9941_CR6","doi-asserted-by":"crossref","first-page":"1713","DOI":"10.1007\/s00373-012-1241-4","volume":"29","author":"CN Campos","year":"2013","unstructured":"Campos CN, Dantas S, de Mello CP (2013) Coloring clique-hypergraphs of circulant graphs. Graphs Combin 29:1713\u20131720","journal-title":"Graphs Combin"},{"key":"9941_CR7","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/j.endm.2008.01.035","volume":"30","author":"MR Cerioli","year":"2008","unstructured":"Cerioli MR, Priscila P (2008) Clique-coloring UE and UEH graphs. Electron Notes Discrete Math 30:201\u2013206","journal-title":"Electron Notes Discrete Math"},{"key":"9941_CR8","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/j.endm.2009.11.047","volume":"35","author":"MR Cerioli","year":"2009","unstructured":"Cerioli MR, Korenchendler AL (2009) Clique-coloring circular-arc graphs. Electron Notes Discrete Math 35:287\u2013292","journal-title":"Electron Notes Discrete Math"},{"key":"9941_CR9","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1002\/jgt.20387","volume":"62","author":"D D\u00e9fossez","year":"2009","unstructured":"D\u00e9fossez D (2009) Complexity of clique-coloring odd-hole free graphs. J Graph Theory 62:139\u2013156","journal-title":"J Graph Theory"},{"key":"9941_CR10","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1002\/jgt.20177","volume":"53","author":"D D\u00e9fossez","year":"2006","unstructured":"D\u00e9fossez D (2006) Clique-coloring some classes of odd-hole free graphs. J Graph Theory 53:233\u2013249","journal-title":"J Graph Theory"},{"key":"9941_CR11","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/0097-3165(91)90083-S","volume":"58","author":"D Duffus","year":"1991","unstructured":"Duffus D, Kierstead HA, Trotter WT (1991) Fibers and ordered set coloring. J Combin Theory Ser A 58:158\u2013164","journal-title":"J Combin Theory Ser A"},{"key":"9941_CR12","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1016\/j.dam.2012.12.021","volume":"164","author":"G Dur\u00e1n","year":"2014","unstructured":"Dur\u00e1n G, Grippo LN, Safe MD (2014) Structural results on circular-arc graphs and circle graphs: a survey and the main open problems. Discrete Appl Math 164:427\u2013443","journal-title":"Discrete Appl Math"},{"key":"9941_CR13","volume-title":"Algorithmic graph theory and perfect graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs, 2nd edn. Academic Press, New York","edition":"2"},{"key":"9941_CR14","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/S0012-365X(01)00054-1","volume":"242","author":"CT Ho\u00e0ng","year":"2002","unstructured":"Ho\u00e0ng CT, McDiarmid C (2002) On the divisibility of graphs. Discrete Math 242:145\u2013156","journal-title":"Discrete Math"},{"key":"9941_CR15","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft J, Tarjan R (1973) Efficient algorithms for graph manipulation. Commun ACM 16:372\u2013378","journal-title":"Commun ACM"},{"key":"9941_CR16","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/s00453-009-9304-5","volume":"59","author":"BL Joeris","year":"2011","unstructured":"Joeris BL, Lin MC, McConnell RM, Spinrad JP, Szwarcfiter JL (2011) Linear-time recognition of Helly circular-arc models and graphs. Algorithmica 59:215\u2013239","journal-title":"Algorithmica"},{"key":"9941_CR17","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0196-6774(02)00221-3","volume":"45","author":"J Kratochv\u00edl","year":"2002","unstructured":"Kratochv\u00edl J, Zs Tuza (2002) On the complexity of bicoloring clique hypergraphs of graphs. J Algorithms 45:40\u201354","journal-title":"J Algorithms"},{"key":"9941_CR18","doi-asserted-by":"crossref","first-page":"3487","DOI":"10.1016\/j.tcs.2011.02.038","volume":"412","author":"D Marx","year":"2011","unstructured":"Marx D (2011) Complexity of clique coloring and related problems. Theoret Comput Sci 412:3487\u20133500","journal-title":"Theoret Comput Sci"},{"key":"9941_CR19","doi-asserted-by":"crossref","first-page":"#R26","DOI":"10.37236\/1458","volume":"6","author":"B Mohar","year":"1999","unstructured":"Mohar B, S\u0306krekovski R (1999) The Gr\u00f6tzsch theorem for the hypergraph of maximal cliques. Electron J Combin 6:#R26","journal-title":"Electron J Combin"},{"key":"9941_CR20","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970401","volume-title":"Graph theory and its applications to problems of society","author":"FS Roberts","year":"1978","unstructured":"Roberts FS (1978) Graph theory and its applications to problems of society. Society for Industrial and Applied Mathematics, Philadelphia"},{"key":"9941_CR21","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"J Rose","year":"1976","unstructured":"Rose J, Tarjan RE, Lueker GS (1976) Algorithmic aspects of vertex elimination on graphs. SIAM J Comput 5:266\u2013283","journal-title":"SIAM J Comput"},{"key":"9941_CR22","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/j.ejc.2013.08.003","volume":"36","author":"EF Shan","year":"2014","unstructured":"Shan EF, Liang ZS, Kang LY (2014) Clique-transversal sets and clique-coloring in planar graphs. Euro J Combin 36:367\u2013376","journal-title":"Euro J Combin"},{"key":"9941_CR23","doi-asserted-by":"crossref","first-page":"1337","DOI":"10.1016\/j.jctb.2008.02.006","volume":"98","author":"C Thomassen","year":"2008","unstructured":"Thomassen C (2008) $$2$$ 2 -List-coloring planar graphs without monochromatic triangles. J Combin Theory Ser B 98:1337\u20131348","journal-title":"J Combin Theory Ser B"},{"key":"9941_CR24","doi-asserted-by":"crossref","first-page":"1257","DOI":"10.1090\/S0002-9904-1970-12628-3","volume":"76","author":"A Tucker","year":"1970","unstructured":"Tucker A (1970) Characterizing circular-arc graphs. Bull Am Math Soc 76:1257\u20131260","journal-title":"Bull Am Math Soc"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9941-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-015-9941-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9941-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9941-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,6]],"date-time":"2020-09-06T18:31:37Z","timestamp":1599417097000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-015-9941-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,1]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["9941"],"URL":"https:\/\/doi.org\/10.1007\/s10878-015-9941-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,1]]}}}