{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T21:59:37Z","timestamp":1761861577220},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2014,5,23]],"date-time":"2014-05-23T00:00:00Z","timestamp":1400803200000},"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":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s00373-014-1446-9","type":"journal-article","created":{"date-parts":[[2014,5,22]],"date-time":"2014-05-22T00:47:52Z","timestamp":1400719672000},"page":"1359-1365","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["On the Complexity of Deciding Whether the Regular Number is at Most Two"],"prefix":"10.1007","volume":"31","author":[{"given":"Ali","family":"Dehghan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad-Reza","family":"Sadeghi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arash","family":"Ahadi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,5,23]]},"reference":[{"issue":"6","key":"1446_CR1","doi-asserted-by":"crossref","first-page":"1294","DOI":"10.1016\/j.disc.2008.01.054","volume":"309","author":"K Bry\u015b","year":"2009","unstructured":"Bry\u015b, K., Lonc, Z.: Polynomial cases of graph decomposition: a complete solution of Holyer\u2019s problem. Discrete Math. 309(6), 1294\u20131326 (2009)","journal-title":"Discrete Math."},{"issue":"4","key":"1446_CR2","doi-asserted-by":"crossref","first-page":"1166","DOI":"10.1137\/S0097539792229507","volume":"26","author":"D Dor","year":"1997","unstructured":"Dor, D., Tarsi, M.: Graph decomposition is NP-complete: a complete proof of Holyer\u2019s conjecture. SIAM J. Comput. 26(4), 1166\u20131187 (1997)","journal-title":"SIAM J. Comput."},{"issue":"2\u20133","key":"1446_CR3","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1080\/09720529.2012.10698371","volume":"15","author":"A Ganesan","year":"2012","unstructured":"Ganesan, A., Iyer, R.R.: The regular number of a graph. J. Discrete Math. Sci. Cryptogr. 15(2\u20133), 149\u2013157 (2012)","journal-title":"J. Discrete Math. Sci. Cryptogr."},{"key":"1446_CR4","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, San Francisco (1979)"},{"issue":"4","key":"1446_CR5","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/0210054","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of some edge-partition problems. SIAM J. Comput. 10(4), 713\u2013717 (1981)","journal-title":"SIAM J. Comput."},{"key":"1446_CR6","doi-asserted-by":"crossref","unstructured":"Kochol, M., Krivo $$\\check{{\\rm n}}$$ n \u02c7 \u00e1kov\u00e1, N., Smejov\u00e1, S., \u0160rankov\u00e1, K.: Complexity of approximation of 3-edge-coloring of graphs. Inf. Process. Lett. 108(4), 238\u2013241 (2008)","DOI":"10.1016\/j.ipl.2008.05.015"},{"issue":"1","key":"1446_CR7","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1080\/09720529.2001.10697919","volume":"4","author":"VR Kulli","year":"2001","unstructured":"Kulli, V.R., Janakiram, B., Iyer, R.R.: Regular number of a graph. J. Discrete Math. Sci. Cryptogr. 4(1), 57\u201364 (2001)","journal-title":"J. Discrete Math. Sci. Cryptogr."},{"issue":"1","key":"1446_CR8","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","volume":"4","author":"D Leven","year":"1983","unstructured":"Leven, D., Galil, Z.: NP-completeness of finding the chromatic index of regular graphs. J. Algorithms 4(1), 35\u201344 (1983)","journal-title":"J. Algorithms"},{"issue":"2","key":"1446_CR9","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0166-218X(95)00107-3","volume":"70","author":"Z Lonc","year":"1996","unstructured":"Lonc, Z.: On the complexity of some edge-partition problems for graphs. Discrete Appl. Math. 70(2), 177\u2013183 (1996)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"1446_CR10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1051\/ro\/1982160201251","volume":"16","author":"B P\u00e9roche","year":"1982","unstructured":"P\u00e9roche, B.: Complexity of the linear arboricity of a graph. RAIRO Rech. Op\u00e9r. 16(2), 125\u2013129 (1982). (in French)","journal-title":"RAIRO Rech. Op\u00e9r."},{"issue":"7\u20138","key":"1446_CR11","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1016\/j.disc.2005.11.059","volume":"307","author":"MD Plummer","year":"2007","unstructured":"Plummer, M.D.: Graph factors and factorization: 1985\u20132003: a survey. Discrete Math. 307(7\u20138), 791\u2013821 (2007)","journal-title":"Discrete Math."},{"key":"1446_CR12","first-page":"25","volume":"3","author":"VG Vizing","year":"1964","unstructured":"Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Diskret. Analiz 3, 25\u201330 (1964)","journal-title":"Diskret. Analiz"},{"key":"1446_CR13","volume-title":"West. Introduction to Graph Theory","author":"B Douglas","year":"1996","unstructured":"Douglas, B.: West. Introduction to Graph Theory. Prentice Hall Inc., Upper Saddle River (1996)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-014-1446-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-014-1446-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-014-1446-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T14:38:40Z","timestamp":1565447920000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-014-1446-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,23]]},"references-count":13,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["1446"],"URL":"https:\/\/doi.org\/10.1007\/s00373-014-1446-9","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,23]]}}}