{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:29:15Z","timestamp":1753885755234,"version":"3.41.2"},"reference-count":31,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","funder":[{"DOI":"10.13039\/501100005276","name":"National Board for Higher Mathematics","doi-asserted-by":"publisher","award":["16646"],"award-info":[{"award-number":["16646"]}],"id":[{"id":"10.13039\/501100005276","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:p> A graph [Formula: see text] is a 3-degree 4-chordal graph if every cycle of length at least five has a chord and the degree of each vertex is at most three. In this paper, we investigate the structure of 3-degree 4-chordal graphs, which is a subclass of 3-degree graphs. We present a structural characterization based on minimal vertex separators and bi-connected components. Many classical problems are known to be NP-complete for 3-degree graphs, and 3-degree 4-chordal graphs are a nontrivial subclass of 3-degree graphs. Using our structural results, we present polynomial-time algorithms for many classical problems which are grouped into (i) subset problems (vertex cover and its variants, feedback vertex set, Steiner tree), (ii) Hamiltonicity and its variants, (iii) graph embedding problems (treewidth, minimum fill-in), and (iv) Coloring problems(rainbow coloring). <\/jats:p>","DOI":"10.1142\/s1793830922500537","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T09:53:00Z","timestamp":1643017980000},"source":"Crossref","is-referenced-by-count":0,"title":["On 3-degree 4-chordal graphs"],"prefix":"10.1142","volume":"15","author":[{"given":"Devarshi","family":"Aggarwal","sequence":"first","affiliation":[{"name":"Indian Institute of Information Technology, Design and Manufacturing, Kancheepuram, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3117-7215","authenticated-orcid":false,"given":"R. Mahendra","family":"Kumar","sequence":"additional","affiliation":[{"name":"Indian Institute of Information Technology, Design and Manufacturing, Kancheepuram, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N.","family":"Sadagopan","sequence":"additional","affiliation":[{"name":"Indian Institute of Information Technology, Design and Manufacturing, Kancheepuram, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,1,22]]},"reference":[{"issue":"2","key":"S1793830922500537BIB003","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1109\/T-AIEE.1932.5056068","volume":"51","author":"Foster R. M.","year":"1932","journal-title":"Trans. Am. Electr. Eng."},{"volume-title":"The foundations of topological graph theory","year":"2012","author":"Bonnington C. P.","key":"S1793830922500537BIB004"},{"issue":"1","key":"S1793830922500537BIB005","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"Dirac G. A.","year":"1961","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg"},{"key":"S1793830922500537BIB006","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"S1793830922500537BIB007","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.dam.2018.06.028","volume":"280","author":"Dhanalakshmi S.","year":"2020","journal-title":"Discrete Appl. Math."},{"key":"S1793830922500537BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90135-3"},{"issue":"1","key":"S1793830922500537BIB009","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","volume":"156","author":"M\u00fcller H.","year":"1996","journal-title":"Discrete Math."},{"key":"S1793830922500537BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90050-4"},{"issue":"1","key":"S1793830922500537BIB011","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF01787477","volume":"6","author":"Hayward R.","year":"1990","journal-title":"Graphs Comb."},{"key":"S1793830922500537BIB012","first-page":"197","volume-title":"Annual Symp. Theoretical Aspects of Computer Science","author":"Bouchitt\u00e9 V.","year":"1999"},{"key":"S1793830922500537BIB013","first-page":"42","volume-title":"Proc. 11th Annual ACM-SIAM Symp. Discrete Algorithms","author":"Hayward R. B.","year":"2000"},{"key":"S1793830922500537BIB014","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/978-3-540-74839-7_23","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Pergel M.","year":"2007"},{"key":"S1793830922500537BIB015","first-page":"429","volume-title":"2012 3rd Int. Conf. Networking and Computing","author":"Takaoka A.","year":"2012"},{"issue":"1","key":"S1793830922500537BIB016","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1006\/jctb.2000.2026","volume":"82","author":"Mohar B.","year":"2001","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"S1793830922500537BIB017","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1016\/0304-3975(94)90185-6","volume":"131","author":"Picouleau C.","year":"1994","journal-title":"Theor. Comput. Sci."},{"key":"S1793830922500537BIB018","doi-asserted-by":"publisher","DOI":"10.1137\/0211015"},{"issue":"1","key":"S1793830922500537BIB019","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.tcs.2005.08.038","volume":"352","author":"Zverovich I. E.","year":"2006","journal-title":"J. Theor. Comput. Sci."},{"key":"S1793830922500537BIB020","first-page":"59","volume-title":"17th Asia and South Pacific Design Automation Conf.","author":"Wang Y.-M.","year":"2012"},{"key":"S1793830922500537BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)00171-H"},{"key":"S1793830922500537BIB022","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90135-3"},{"issue":"1","key":"S1793830922500537BIB023","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/990518.990521","volume":"7","author":"Krishnamoorthy M. S.","year":"1975","journal-title":"ACM SIGACT News"},{"issue":"2","key":"S1793830922500537BIB024","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1006\/jagm.1995.1037","volume":"19","author":"Kloks T.","year":"1995","journal-title":"J. Algorithms"},{"issue":"4","key":"S1793830922500537BIB025","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"Garey M. R.","year":"1977","journal-title":"SIAM J. Appl. Math."},{"key":"S1793830922500537BIB026","first-page":"1017","volume-title":"IEEE Int. Symp. Circuits and Systems","author":"Watanabe T.","year":"1991"},{"key":"S1793830922500537BIB027","volume-title":"Introduction to Graph Theory","volume":"2","author":"West B. D.","year":"1996"},{"key":"S1793830922500537BIB028","first-page":"429","volume-title":"2012 3rd Int. Conf. Networking and Computing","author":"Takaoka A.","year":"2012"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1979","author":"Garey M. R.","key":"S1793830922500537BIB029"},{"issue":"1","key":"S1793830922500537BIB030","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"Yannakakis M.","year":"1981","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"S1793830922500537BIB031","doi-asserted-by":"publisher","DOI":"10.21136\/MB.2008.133947"},{"key":"S1793830922500537BIB032","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-012-1243-2"},{"issue":"3","key":"S1793830922500537BIB033","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1007\/s10878-009-9250-9","volume":"21","author":"Chakraborty S.","year":"2009","journal-title":"J. Comb. Optim."}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830922500537","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,3]],"date-time":"2023-02-03T05:23:35Z","timestamp":1675401815000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S1793830922500537"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,22]]},"references-count":31,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["10.1142\/S1793830922500537"],"URL":"https:\/\/doi.org\/10.1142\/s1793830922500537","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2022,1,22]]},"article-number":"2250053"}}