{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:45:14Z","timestamp":1759063514872,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319286778"},{"type":"electronic","value":"9783319286785"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-28678-5_9","type":"book-chapter","created":{"date-parts":[[2016,1,8]],"date-time":"2016-01-08T10:14:18Z","timestamp":1452248058000},"page":"121-134","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Rainbow Domination and Related Problems on Some Classes of Perfect Graphs"],"prefix":"10.1007","author":[{"given":"Wing-Kai","family":"Hon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ton","family":"Kloks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hsiang-Hsuan","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hung-Lung","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,9]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"1766","DOI":"10.1016\/j.disc.2008.02.025","volume":"309","author":"R Aharoni","year":"2009","unstructured":"Aharoni, R., Szab\u00f3, T.: Vizing\u2019s conjecture for chordal graphs. Discrete Math. 309, 1766\u20131768 (2009)","journal-title":"Discrete Math."},{"issue":"1","key":"9_CR2","doi-asserted-by":"crossref","first-page":"213","DOI":"10.11650\/twjm\/1500602498","volume":"12","author":"B Bres\u0306ar","year":"2008","unstructured":"Bres\u0306ar, B., Henning, M., Rall, D.: Rainbow domination in graphs. Taiwanese J. Math. 12(1), 213\u2013225 (2008)","journal-title":"Taiwanese J. Math."},{"issue":"17","key":"9_CR3","doi-asserted-by":"publisher","first-page":"2394","DOI":"10.1016\/j.dam.2007.07.018","volume":"155","author":"B Bres\u0306ar","year":"2007","unstructured":"Bres\u0306ar, B., S\u0306umenjak, T.: On 2-rainbow domination in graphs. Discrete Appl. Math. 155(17), 2394\u20132400 (2007)","journal-title":"Discrete Appl. Math."},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","volume":"19","author":"A Bertossi","year":"1984","unstructured":"Bertossi, A.: Dominating sets for split and bipartite graphs. Inf. Process. Lett. 19, 37\u201340 (1984)","journal-title":"Inf. Process. Lett."},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"1277","DOI":"10.1137\/060664690","volume":"22","author":"A Bretscher","year":"2008","unstructured":"Bretscher, A., Corneil, D., Habib, M., Paul, C.: A simple linear time LexBFS cograph recognition algorithm. SIAM J. Discrete Math. 22, 1277\u20131296 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0012-365X(92)00468-7","volume":"127","author":"P Cameron","year":"1994","unstructured":"Cameron, P.: Two-graphs and trees. Discrete Math. 127, 63\u201374 (1994)","journal-title":"Discrete Math."},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/j.dam.2009.08.010","volume":"158","author":"G Chang","year":"2010","unstructured":"Chang, G., Wu, J., Zhu, X.: Rainbow domination on trees. Discrete Appl. Math. 158, 8\u201312 (2010)","journal-title":"Discrete Appl. Math."},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"1395","DOI":"10.1016\/j.dam.2013.01.024","volume":"161","author":"G Chang","year":"2013","unstructured":"Chang, G., Li, B., Wu, J.: Rainbow domination and related problems on strongly chordal graphs. Discrete Appl. Math. 161, 1395\u20131401 (2013)","journal-title":"Discrete Appl. Math."},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.ipl.2007.12.009","volume":"107","author":"F Chu","year":"2008","unstructured":"Chu, F.: A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements. Inf. Process. Lett. 107, 7\u201312 (2008)","journal-title":"Inf. Process. Lett."},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D Corneil","year":"1981","unstructured":"Corneil, D., Lerchs, H., Stewart-Burlingham, L.: Complement reducible graphs. Discrete Appl. Math. 3, 163\u2013174 (1981)","journal-title":"Discrete Appl. Math."},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D Corneil","year":"1985","unstructured":"Corneil, D., Perl, Y., Stewart, L.: A linear recognition algorithm for cographs. SIAM J. Comput. 14, 926\u2013934 (1985)","journal-title":"SIAM J. Comput."},{"key":"9_CR12","volume-title":"Handbook of Graph Grammars and Graph Transformations","author":"B Courcelle","year":"1997","unstructured":"Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. Handbook of Graph Grammars and Graph Transformations. World Scientific Publishing Co. Inc., River Edge (1997)"},{"key":"9_CR13","unstructured":"Domke, G., Hedetniemi, S., Laskar, R., Fricke, G.: Relationships between integer and fractional parameters of graphs. In: Alavi, Y., Chartrand, G., Oellermann, O., Schwenk, A. (eds.) Graph Theory, Combinatorics, and Applications: Proceedings of the 6th Quadrennial International Conference on the Theory and Applications of Graphs 1 (Kalamzaoo 1988), pp. 371\u2013387. Wiley (1991)"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0166-218X(84)90061-1","volume":"7","author":"M Farber","year":"1984","unstructured":"Farber, M.: Domination, independent domination, and duality in strongly chordal graphs. Discrete Appl. Math. 7, 115\u2013130 (1984)","journal-title":"Discrete Appl. Math."},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare graphen. Acta Math. Acad. Sci. Hung. 18, 25\u201366 (1967). A translation appears in Ram\u00edrez-Alfons\u00edn, J., Reed, B. (eds.): Perfect Graphs. Interscience series in discrete mathematics and optimization. John Wiley & Sons, Chichester (2001)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"P Gilmore","year":"1964","unstructured":"Gilmore, P., Hoffman, A.: A characterization of comparability graphs and of interval graphs. Canadian J. Math. 16, 539\u2013548 (1964)","journal-title":"Canadian J. Math."},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0012-365X(78)90178-4","volume":"24","author":"M Golumbic","year":"1978","unstructured":"Golumbic, M.: Trivially perfect graphs. Discrete Math. 24, 105\u2013107 (1978)","journal-title":"Discrete Math."},{"key":"9_CR18","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.dam.2004.01.011","volume":"145","author":"M Habib","year":"2005","unstructured":"Habib, M., Paul, C.: A simple linear time algorithm for cograph recognition. Discrete Appl. Math. 145, 183\u2013197 (2005)","journal-title":"Discrete Appl. Math."},{"key":"9_CR19","unstructured":"Ho\u00e0ng, C.: A class of perfect graphs, Master\u2019s Thesis. School of Computer Science, McGill University, Montreal (1983)"},{"key":"9_CR20","unstructured":"Hon, W.-K., Kloks, T., Liu, H.-H., Wang, H.-L.: Rainbow domination and related problems on some classes of perfect graphs (2015). \n                    arXiv:1502.07492\n                    \n                   [cs.DM]"},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"389","DOI":"10.7151\/dmgt.1238","volume":"24","author":"B Hartnell","year":"2004","unstructured":"Hartnell, B., Rall, D.: On dominating the cartesian product of a graph and \n                    \n                      \n                    \n                    $$K_2$$\n                    \n                      \n                        \n                          K\n                          2\n                        \n                      \n                    \n                  . Discussiones Mathematicae Graph Theory 24, 389\u2013402 (2004)","journal-title":"Discussiones Mathematicae Graph Theory"},{"key":"9_CR22","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0166-218X(92)90036-A","volume":"35","author":"B Jamison","year":"1992","unstructured":"Jamison, B., Olariu, S.: A tree representation for \n                    \n                      \n                    \n                    $$P_4$$\n                    \n                      \n                        \n                          P\n                          4\n                        \n                      \n                    \n                  -sparse graphs. Discrete Appl. Math. 35, 115\u2013129 (1992)","journal-title":"Discrete Appl. Math."},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Pai, K., Chiu, W.: 3-Rainbow domination number in graphs. In: Proceedings of the Institute of Industrial Engineers Asian Conference 2013, pp. 713\u2013720. Springer, Science+Business Media Singapore (2013)","DOI":"10.1007\/978-981-4451-98-7_86"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"van Rooij, J., Exact exponential-time algorithms for domination problems in graphs, Ph.D. Thesis, Utrecht University (2011)","DOI":"10.1007\/s00453-011-9546-x"},{"key":"9_CR25","doi-asserted-by":"publisher","first-page":"2147","DOI":"10.1016\/j.dam.2011.07.001","volume":"159","author":"J Rooij van","year":"2011","unstructured":"van Rooij, J., Bodlaender, H.: Exact algorithms for dominating set. Discrete Appl. Math. 159, 2147\u20132164 (2011)","journal-title":"Discrete Appl. Math."},{"key":"9_CR26","doi-asserted-by":"publisher","first-page":"409","DOI":"10.7151\/dmgt.1371","volume":"27","author":"R Rubalcaba","year":"2007","unstructured":"Rubalcaba, R., Slater, P.: Efficient \n                    \n                      \n                    \n                    $$(j, k)$$\n                    \n                      \n                        \n                          (\n                          j\n                          ,\n                          k\n                          )\n                        \n                      \n                    \n                  -domination. Discussiones Mathematicae Graph Theory 27, 409\u2013423 (2007)","journal-title":"Discussiones Mathematicae Graph Theory"},{"key":"9_CR27","first-page":"47","volume":"51","author":"R Rubalcaba","year":"2007","unstructured":"Rubalcaba, R., Slater, P.: A note on obtaining \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                   dominating sets from a \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -dominating function on a tree. Bull. Inst. Combin. Appl. 51, 47\u201354 (2007)","journal-title":"Bull. Inst. Combin. Appl."},{"key":"9_CR28","unstructured":"S\u0306umenjak, T., Rall, D., Tepeh, A.: Rainbow domination in the lexicographic product of graphs (2012). \n                    arXiv:1210.0514"},{"key":"9_CR29","first-page":"117","volume":"23","author":"V Vizing","year":"1968","unstructured":"Vizing, V.: Some unsolved problems in graph theory. Uspehi Mat. Naukno. (in Russian) 23, 117\u2013134 (1968)","journal-title":"Uspehi Mat. Naukno. (in Russian)"},{"key":"9_CR30","series-title":"Smart Innovation, Systems and Technologies","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-642-35452-6_8","volume-title":"Advances in Intelligent Systems and Applications - Volume 1","author":"C Yen","year":"2013","unstructured":"Yen, C.: 2-Rainbow domination and its practical variations on weighted graphs. In: Chang, R.-S., Jain, L.C., Peng, S.-L. (eds.) Advances in Intelligent Systems and Applications - Volume 1. Smart Innovation, Systems and Technologies, vol. 20, pp. 59\u201368. Springer, Berlin (2013)"}],"container-title":["Lecture Notes in Computer Science","Topics in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-28678-5_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,7]],"date-time":"2020-01-07T20:05:03Z","timestamp":1578427503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-28678-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319286778","9783319286785"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-28678-5_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"9 January 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}