{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:09Z","timestamp":1759638429601,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,3,6]],"date-time":"2018-03-06T00:00:00Z","timestamp":1520294400000},"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":[[2018,5]]},"DOI":"10.1007\/s10878-018-0272-z","type":"journal-article","created":{"date-parts":[[2018,3,6]],"date-time":"2018-03-06T09:46:57Z","timestamp":1520329617000},"page":"1312-1329","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the algorithmic aspects of strong subcoloring"],"prefix":"10.1007","volume":"35","author":[{"given":"M. A.","family":"Shalu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Vijayakumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. Devi","family":"Yamini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7745-3935","authenticated-orcid":false,"given":"T. P.","family":"Sandhya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,6]]},"reference":[{"key":"272_CR1","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0012-365X(89)90196-9","volume":"74","author":"MO Albertson","year":"1989","unstructured":"Albertson MO, Jamison RE, Hedetniemi ST, Locke SC (1989) The subchromatic number of a graph. Discrete Math 74:33\u201349","journal-title":"Discrete Math"},{"key":"272_CR2","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.dam.2017.06.013","volume":"230","author":"G Bagan","year":"2017","unstructured":"Bagan G, Merouane HB, Haddad M, Kheddouci H (2017) On some domination colorings of graphs. Discrete Appl Math 230:34\u201350","journal-title":"Discrete Appl Math"},{"key":"272_CR3","doi-asserted-by":"publisher","first-page":"194197","DOI":"10.1017\/S030500410002168X","volume":"37","author":"RL Brooks","year":"1941","unstructured":"Brooks RL (1941) On colouring the nodes of a network. Math Proc Camb Philos Soc 37:194197","journal-title":"Math Proc Camb Philos Soc"},{"key":"272_CR4","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s00607-002-1461-1","volume":"69","author":"H Broersma","year":"2002","unstructured":"Broersma H, Fomin FV, Nesetril J, Woeginger G (2002) More about subcolorings. Computing 69:187\u2013203","journal-title":"Computing"},{"key":"272_CR5","doi-asserted-by":"crossref","unstructured":"Fiala J, Jansen K, Le VB, Seidel E (2001) Graph subcolorings: complexity and algorithms. In: Brandst\n                    \n                      \n                    \n                    $$\\ddot{\\text{a}}$$\n                    \n                      \n                        \n                          a\n                          \u00a8\n                        \n                      \n                    \n                  dt A, Le VB (eds) Graph-theoretic concepts in computer science. WG 2001. Lecture notes in computer science, vol 2204. Springer, Berlin","DOI":"10.1007\/3-540-45477-2_15"},{"key":"272_CR6","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1137\/S0895480101395245","volume":"16","author":"J Fiala","year":"2003","unstructured":"Fiala J, Jansen K, Le VB, Seidel E (2003) Graph subcolorings: complexity and algorithms. SIAM J Discrete Math 16:635\u2013650","journal-title":"SIAM J Discrete Math"},{"key":"272_CR7","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1142\/S1793830910000693","volume":"2","author":"R Gandhi","year":"2010","unstructured":"Gandhi R, Greening B Jr, Pemmaraju S, Raman R (2010) Sub-coloring and hypo-coloring of interval graphs. Discrete Math Algorithms Appl 2:331\u2013345","journal-title":"Discrete Math Algorithms Appl"},{"key":"272_CR8","volume-title":"Computers and intractability; a guide to the theory of NP-completeness","author":"MR Garey","year":"1990","unstructured":"Garey MR, Johnson DS (1990) Computers and intractability; a guide to the theory of NP-completeness. W. H. Freeman & Co., New York"},{"key":"272_CR9","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F Gavril","year":"1972","unstructured":"Gavril F (1972) Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J Comput 1:180\u2013187","journal-title":"SIAM J Comput"},{"key":"272_CR10","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer I (1981) The NP-completeness of edge-colouring. SIAM J Comput 10:718\u2013720","journal-title":"SIAM J Comput"},{"key":"272_CR11","doi-asserted-by":"crossref","unstructured":"Illuri M, Renjith P, Sadagopan N (2016) Complexity of steiner tree in split graphs\u2014dichotomy results. In: Algorithms and discrete applied mathematics, LNCS, vol 9602, pp 308\u2013325","DOI":"10.1007\/978-3-319-29221-2_27"},{"key":"272_CR12","volume-title":"Complexity of computer computations","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum Press, New York"},{"key":"272_CR13","unstructured":"Kral D, Kratochvil J, Tuza Z, Woeginger GJ (2001) Complexity of coloring graphs without forbidden induced subgraphs. In: Proceedings of the 27th international workshop on graph-theoretic concepts in computer science WG\u201901, LNCS, vol 2204, pp 254\u2013262"},{"key":"272_CR14","doi-asserted-by":"crossref","unstructured":"Krithika R, Rai A, Saurabh S, Tale P (2017) Parameterized and exact algorithms for class domination coloring. In: Proceedings of the 43\n                    \n                      \n                    \n                    $$^{{\\rm rd}}$$\n                    \n                      \n                        \n                          \n                          rd\n                        \n                      \n                    \n                   conference on current trends in theory and practice of computer science (SOFSEM), LNCS, vol 10139, pp 336\u2013349","DOI":"10.1007\/978-3-319-51963-0_26"},{"key":"272_CR15","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/s00373-014-1407-3","volume":"31","author":"HB Merouane","year":"2015","unstructured":"Merouane HB, Haddad M, Chellali M, Kheddouci H (2015) Dominated colorings of graphs. Graphs Comb 31:713\u2013727","journal-title":"Graphs Comb"},{"key":"272_CR16","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty GJ (1980) On maximal independent sets of vertices in claw-free graphs. J Comb Theory B 28:284\u2013304","journal-title":"J Comb Theory B"},{"key":"272_CR17","doi-asserted-by":"crossref","unstructured":"Shalu MA, Sandhya TP (2016) The cd-coloring of Graphs. In: Proceedings of the second international conference on algorithms and discrete applied mathematics (CALDAM), LNCS, vol 9602, pp 337\u2013348","DOI":"10.1007\/978-3-319-29221-2_29"},{"key":"272_CR18","doi-asserted-by":"crossref","unstructured":"Shalu MA, Vijayakumar S, Sandhya TP (2017) A lower bound of the cd-chromatic number and its complexity. In: Proceedings of the third international conference on algorithms and discrete applied mathematics (CALDAM), LNCS, vol 10156, pp 344\u2013355","DOI":"10.1007\/978-3-319-53007-9_30"},{"key":"272_CR19","unstructured":"Stacho J (2008) Complexity of generalized colourings of chordal graphs. Ph.D. Thesis, Simon Fraser University"},{"key":"272_CR20","first-page":"301","volume":"18","author":"YB Venkatakrishnan","year":"2014","unstructured":"Venkatakrishnan YB, Swaminathan V (2014) Color class domination numbers of some classes of graphs. Algebra Discrete Math 18:301\u2013305","journal-title":"Algebra Discrete Math"},{"key":"272_CR21","first-page":"25","volume":"3","author":"VG Vizing","year":"1964","unstructured":"Vizing VG (1964) On an estimate of the chromatic class of a p-graph. Diskret Analiz 3:25\u201330 (Russian)","journal-title":"Diskret Analiz"},{"key":"272_CR22","volume-title":"Introduction to graph theory","author":"DB West","year":"2000","unstructured":"West DB (2000) Introduction to graph theory, 2nd edn. Prentice-Hall, Upper Saddle River","edition":"2"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0272-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0272-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0272-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T23:23:45Z","timestamp":1551828225000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0272-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,6]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["272"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0272-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2018,3,6]]},"assertion":[{"value":"6 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}