{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T20:16:17Z","timestamp":1767212177354,"version":"3.40.5"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p>A [Formula: see text] vertex coloring of a graph [Formula: see text] partitions the vertex set into [Formula: see text] color classes (or independent sets). In minimum vertex coloring problem, the aim is to minimize the number of colors used in a given graph. Here, we consider three variations of vertex coloring problem in which (i) each vertex in [Formula: see text] dominates a color class, (ii) each color class is dominated by a vertex and (iii) each vertex is dominating a color class and each color class is dominated by a vertex. These minimization problems are known as Min-Dominator-Coloring, Min-CD-Coloring and Min-Domination-Coloring, respectively. In this paper, we present approximation hardness results for these problems for some restricted class of graphs.<\/jats:p>","DOI":"10.1142\/s179383092050086x","type":"journal-article","created":{"date-parts":[[2020,7,1]],"date-time":"2020-07-01T12:11:18Z","timestamp":1593605478000},"page":"2050086","source":"Crossref","is-referenced-by-count":4,"title":["Lower bounds on approximating some variations of vertex coloring problem over restricted graph classes"],"prefix":"10.1142","volume":"12","author":[{"given":"Sayani","family":"Das","sequence":"first","affiliation":[{"name":"Department of Mathematics, IIT Madras, Chennai 600036, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8393-9109","authenticated-orcid":false,"given":"Sounaka","family":"Mishra","sequence":"additional","affiliation":[{"name":"Department of Mathematics, IIT Madras, Chennai 600036, India"}]}],"member":"219","published-online":{"date-parts":[[2020,8,27]]},"reference":[{"issue":"4","key":"S179383092050086XBIB001","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/s12044-012-0092-5","volume":"122","author":"Arumugam S.","year":"2012","journal-title":"Proc. Math. Sci."},{"key":"S179383092050086XBIB002","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/978-3-642-25011-8_2","volume-title":"Int. Workshop on Combinatorial Algorithms","author":"Arumugam S.","year":"2011"},{"issue":"1","key":"S179383092050086XBIB005","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s00373-010-1012-z","volume":"28","author":"Chellali M.","year":"2012","journal-title":"Graphs Combinatorics"},{"key":"S179383092050086XBIB006","first-page":"132","volume-title":"Int. Conf. on Computational Science and its Applications","author":"Chen Y. H.","year":"2014"},{"issue":"4","key":"S179383092050086XBIB007","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"Feige U.","year":"1998","journal-title":"J. ACM"},{"key":"S179383092050086XBIB008","first-page":"25","volume":"52","author":"Gera R.","year":"2007","journal-title":"Graph Theory Notes New York"},{"key":"S179383092050086XBIB009","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1109\/ITNG.2007.142","volume-title":"Fourth Int. Conf. Information Technology (ITNG\u201907)","author":"Gera R.","year":"2007"},{"key":"S179383092050086XBIB010","first-page":"19","volume":"181","author":"Gera R.","year":"2006","journal-title":"Congress"},{"issue":"1","key":"S179383092050086XBIB011","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF01788689","volume":"5","author":"Hayward R.","year":"1989","journal-title":"Graphs Combin."},{"key":"S179383092050086XBIB012","first-page":"144","volume-title":"Int. Conf. Theoretical Computer Science and Discrete Mathematics","author":"Jeyaseeli J. M.","year":"2016"},{"key":"S179383092050086XBIB013","first-page":"336","volume-title":"Int. Conf. Current Trends in Theory and Practice of Informatics","author":"Krithika R.","year":"2017"},{"issue":"3","key":"S179383092050086XBIB014","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1007\/s00373-014-1407-3","volume":"31","author":"Merouane H. B.","year":"2015","journal-title":"Graphs Combin."},{"key":"S179383092050086XBIB015","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.dam.2018.03.004","volume":"280","author":"Shalu M.","year":"2020","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"S179383092050086XBIB016","doi-asserted-by":"crossref","first-page":"28","DOI":"10.9790\/5728-0362833","volume":"3","author":"Sudhakaraiah A.","year":"2012","journal-title":"IOSR J. Math."},{"volume-title":"Mathematical and Experimental Physics","year":"2010","author":"Swaminathan V.","key":"S179383092050086XBIB017"},{"key":"S179383092050086XBIB018","first-page":"233","volume":"12","author":"Venkatakrishnan Y.","year":"2010","journal-title":"Adv. Model. Optim."},{"issue":"2","key":"S179383092050086XBIB019","first-page":"301","volume":"18","author":"Venkatakrishnan Y. B.","year":"2014","journal-title":"Algebra Discrete Math."},{"key":"S179383092050086XBIB021","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1145\/1132516.1132612","volume-title":"Proc. Thirty-Eighth Annual ACM Symp. Theory of Computing","author":"Zuckerman D.","year":"2006"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S179383092050086X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T16:31:04Z","timestamp":1616430664000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S179383092050086X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,27]]},"references-count":18,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["10.1142\/S179383092050086X"],"URL":"https:\/\/doi.org\/10.1142\/s179383092050086x","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2020,8,27]]}}}