{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T09:00:42Z","timestamp":1764061242625,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T00:00:00Z","timestamp":1712361600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T00:00:00Z","timestamp":1712361600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","award":["PDF\/2021\/003452","MTR\/2020\/000497","SRG\/2020\/001162"],"award-info":[{"award-number":["PDF\/2021\/003452","MTR\/2020\/000497","SRG\/2020\/001162"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["FWF START Project Y1329"],"award-info":[{"award-number":["FWF START Project Y1329"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,7]]},"DOI":"10.1007\/s00453-024-01227-2","type":"journal-article","created":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T08:02:14Z","timestamp":1712390534000},"page":"2250-2288","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Conflict-Free Coloring: Graphs of Bounded Clique-Width and Intersection Graphs"],"prefix":"10.1007","volume":"86","author":[{"given":"Sriram","family":"Bhyravarapu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim A.","family":"Hartmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hung P.","family":"Hoang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subrahmanyam","family":"Kalyanasundaram","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I.","family":"Vinod Reddy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,6]]},"reference":[{"issue":"4","key":"1227_CR1","doi-asserted-by":"publisher","first-page":"2675","DOI":"10.1137\/17M1146579","volume":"32","author":"Z Abel","year":"2018","unstructured":"Abel, Z., Alvarez, V., Demaine, E.D., Fekete, S.P., Gour, A., Hesterberg, A., Keldenich, P., Scheffer, C.: Conflict-free coloring of graphs. SIAM J. Discret. Math. 32(4), 2675\u20132702 (2018)","journal-title":"SIAM J. Discret. Math."},{"key":"1227_CR2","unstructured":"Agrawal, A., Ashok, P., Reddy, M.M., Saurabh, S., Yadav, D.: FPT algorithms for conflict-free coloring of graphs and chromatic terrain guarding. arXiv:1905.01822 (2019)"},{"issue":"2","key":"1227_CR3","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"41","author":"H-J Bandelt","year":"1986","unstructured":"Bandelt, H.-J., Mulder, H.M.: Distance-hereditary graphs. J. Comb. Theory Ser. B 41(2), 182\u2013208 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1227_CR4","doi-asserted-by":"crossref","unstructured":"Bergougnoux, B., Dreier, J., Jaffke, L.: A logic-based algorithmic meta-theorem for mim-width. In: Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22\u201325, 2023, pp. 3282\u20133304. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch125"},{"key":"1227_CR5","doi-asserted-by":"crossref","unstructured":"Bhyravarapu, S., Hartmann, T.A., Kalyanasundaram, S., VinodReddy, I.: Conflict-free coloring: Graphs of bounded clique width and intersection graphs. In: Combinatorial Algorithms, pp. 92\u2013106. Springer, Cham (2021)","DOI":"10.1007\/978-3-030-79987-8_7"},{"key":"1227_CR6","unstructured":"Bhyravarapu, S., Kalyanasundaram, S., Mathew, R.: Conflict-Free Coloring on Claw-Free Graphs and Interval Graphs. In: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS: volume 241 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 19:1\u201319:14, p. 2022. Dagstuhl, Germany (2022)"},{"key":"1227_CR7","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Kolay, S., Pieterse, A.: Parameterized complexity of conflict-free graph coloring. In: Algorithms and Data Structures\u201416th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5\u20137, 2019, Proceedings, pp. 168\u2013180 (2019)","DOI":"10.1007\/978-3-030-24766-9_13"},{"issue":"3","key":"1227_CR8","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"DG Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Burlingham, L.S.: Complement reducible graphs. Discrete Appl. Math. 3(3), 163\u2013174 (1981)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"1227_CR9","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discret. Appl. Math."},{"key":"1227_CR10","volume-title":"D\u00e1niel Marx","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D.: D\u00e1niel Marx. Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, Marcin Pilipczuk (2015)"},{"key":"1227_CR11","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H de Fraysseix","year":"1990","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10, 41\u201351 (1990)","journal-title":"Combinatorica"},{"key":"1227_CR12","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 5th edn. Springer Publishing Company, Incorporated (2017)","DOI":"10.1007\/978-3-662-53622-3"},{"key":"1227_CR13","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R. Fundamentals of Parameterized Complexity. Springer Publishing Company, Incorporated (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"1","key":"1227_CR14","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1137\/S0097539702431840","volume":"33","author":"G Even","year":"2004","unstructured":"Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput. 33(1), 94\u2013136 (2004)","journal-title":"SIAM J. Comput."},{"issue":"03","key":"1227_CR15","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1142\/S0218195918500085","volume":"28","author":"SP Fekete","year":"2018","unstructured":"Fekete, S.P., Keldenich, P.: Conflict-free coloring of intersection graphs. Int. J. Comput. Geom. Appl. 28(03), 289\u2013307 (2018)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"22","key":"1227_CR16","doi-asserted-by":"publisher","first-page":"2906","DOI":"10.1016\/j.disc.2006.04.043","volume":"307","author":"F Gardi","year":"2007","unstructured":"Gardi, F.: The roberts characterization of proper and unit interval graphs. Discret. Math. 307(22), 2906\u20132908 (2007)","journal-title":"Discret. Math."},{"key":"1227_CR17","doi-asserted-by":"publisher","first-page":"1858","DOI":"10.1016\/j.dam.2009.01.015","volume":"157","author":"L Gargano","year":"2009","unstructured":"Gargano, L., Rescigno, A.: Collision-free path coloring with application to minimum-delay gathering in sensor networks. Discrete Appl. Math. 157, 1858\u20131872 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"C","key":"1227_CR18","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.tcs.2014.11.029","volume":"566","author":"L Gargano","year":"2015","unstructured":"Gargano, L., Rescigno, A.A.: Complexity of conflict-free colorings of graphs. Theor. Comput. Sci. 566(C), 39\u201349 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1227_CR19","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1017\/S0963548313000540","volume":"23","author":"R Glebov","year":"2014","unstructured":"Glebov, R., Szab\u00f3, T., Tardos, G.: Conflict-free colouring of graphs. Combin. Probab. Comput. 23(3), 434\u2013448 (2014)","journal-title":"Combin. Probab. Comput."},{"issue":"03","key":"1227_CR20","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"MC Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(03), 423\u2013443 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1227_CR21","unstructured":"Gonzalez, C-L., Mann, F.: On d-stable locally checkable problems on bounded mim-width graphs. arXiv:2203.15724 (2022)"},{"key":"1227_CR22","unstructured":"Gupta, S., Kalyanasundaram, S., Mathew, R.: Extremal results on conflict-free coloring (2023)"},{"issue":"112","key":"1227_CR23","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1093\/qmath\/28.4.417","volume":"28","author":"E Howorka","year":"1977","unstructured":"Howorka, E.: A characterization of distance-hereditary graphs. Quart. J. Math. Oxford Ser. 28(112), 417\u2013420 (1977)","journal-title":"Quart. J. Math. Oxford Ser."},{"issue":"3","key":"1227_CR24","doi-asserted-by":"publisher","first-page":"2009","DOI":"10.1137\/19M1272111","volume":"34","author":"F Huang","year":"2020","unstructured":"Huang, F., Guo, S., Yuan, J.: A short note on open-neighborhood conflict-free colorings of graphs. SIAM J. Discret. Math. 34(3), 2009\u20132015 (2020)","journal-title":"SIAM J. Discret. Math."},{"key":"1227_CR25","unstructured":"Jensen, T.R., Toft, B.: Graph coloring problems. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York, 1995. A Wiley-Interscience Publication"},{"key":"1227_CR26","first-page":"1","volume":"65","author":"C Keller","year":"2020","unstructured":"Keller, C., Rok, A., Smorodinsky, S.: Conflict-free coloring of string graphs. Discrete Comput. Geom. 65, 1\u201336 (2020)","journal-title":"Discrete Comput. Geom."},{"key":"1227_CR27","doi-asserted-by":"crossref","unstructured":"Krishnan, P., Mathew, R., Kalyanasundaram, S.: Pliable index coding via conflict-free colorings of hypergraphs. In: IEEE International Symposium on Information Theory, ISIT 2021, Melbourne, Australia, July 12-20, 2021, pp. 214\u2013219. IEEE (2021)","DOI":"10.1109\/ISIT45174.2021.9518120"},{"issue":"3","key":"1227_CR28","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0097-3165(78)90022-5","volume":"25","author":"L Lov\u00e1sz","year":"1978","unstructured":"Lov\u00e1sz, L.: Kneser\u2019s conjecture, chromatic number, and homotopy. J. Comb. Theory Ser. A 25(3), 319\u2013324 (1978)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"2","key":"1227_CR29","doi-asserted-by":"publisher","first-page":"323","DOI":"10.5540\/tema.2019.020.02.323","volume":"20","author":"L Markenzon","year":"2019","unstructured":"Markenzon, L., Waga, C.F.E.M.: Characterizing block graphs in terms of one-vertex extensions. TEMA Tend. Mat. Apl. Comput. 20(2), 323\u2013330 (2019)","journal-title":"TEMA Tend. Mat. Apl. Comput."},{"issue":"2","key":"1227_CR30","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/1346330.1346336","volume":"55","author":"W Mulzer","year":"2008","unstructured":"Mulzer, W., Rote, G.: Minimum-weight triangulation is NP-hard. J. ACM 55(2), 29 (2008)","journal-title":"J. ACM"},{"issue":"5","key":"1227_CR31","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1017\/S0963548309990290","volume":"18","author":"J Pach","year":"2009","unstructured":"Pach, J., Tardos, G.: Conflict-free colourings of graphs and hypergraphs. Comb. Probab. Comput. 18(5), 819\u2013834 (2009)","journal-title":"Comb. Probab. Comput."},{"key":"1227_CR32","doi-asserted-by":"crossref","unstructured":"Smorodinsky, S.: Conflict-free coloring and its applications. In: Geometry-Intuitive, Discrete, and Convex, pp. 331\u2013389. Springer (2013)","DOI":"10.1007\/978-3-642-41498-5_12"},{"key":"1227_CR33","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2018.05.025","volume":"745","author":"I Vinod Reddy","year":"2018","unstructured":"Vinod Reddy, I.: Parameterized algorithms for conflict-free colorings of graphs. Theor. Comput. Sci. 745, 53\u201362 (2018)","journal-title":"Theor. Comput. Sci."},{"key":"1227_CR34","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1016\/j.procs.2015.10.092","volume":"70","author":"VP Vijayan","year":"2015","unstructured":"Vijayan, V.P., Gopinathan, E.: Design of collision-free nearest neighbor assertion and load balancing in sensor network system. Procedia Comput. Sci. 70, 508\u2013514 (2015)","journal-title":"Procedia Comput. Sci."},{"key":"1227_CR35","volume-title":"Introduction to Graph Theory","author":"DB West","year":"1996","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice Hall Inc, Upper Saddle River, NJ (1996)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01227-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01227-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01227-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,17]],"date-time":"2024-07-17T16:04:03Z","timestamp":1721232243000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01227-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,6]]},"references-count":35,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["1227"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01227-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,4,6]]},"assertion":[{"value":"28 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}