{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T19:46:03Z","timestamp":1720640763537},"reference-count":61,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2002,7,1]],"date-time":"2002-07-01T00:00:00Z","timestamp":1025481600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electronic Notes in Discrete Mathematics"],"published-print":{"date-parts":[[2002,7]]},"DOI":"10.1016\/s1571-0653(04)00055-1","type":"journal-article","created":{"date-parts":[[2004,10,15]],"date-time":"2004-10-15T11:21:27Z","timestamp":1097839287000},"page":"63-80","source":"Crossref","is-referenced-by-count":2,"special_numbering":"C","title":["More Progress on Tough Graphs - The Y2K Report"],"prefix":"10.1016","volume":"11","author":[{"given":"Doug","family":"Bauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hajo","family":"Broersma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edward","family":"Schmeichel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB1","first-page":"71","article-title":"Chordal graphs and some of their derived graphs","volume":"53","author":"Balakrishnan","year":"1986","journal-title":"Congr. Numer"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB2","article-title":"Polynomial algorithms that prove an NP-hard hypothesis implies and NP-hard conclusion","author":"Bauer","year":"2000","journal-title":"Preprint"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB3","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1002\/jgt.3190180602","article-title":"On hamiltonian properties of 2-tough graphs","volume":"18","author":"Bauer","year":"1994","journal-title":"J. Graph Theory"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB4","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S0166-218X(99)00141-9","article-title":"Not every 2-tough graph is hamiltonian","volume":"99","author":"Bauer","year":"2000","journal-title":"Discrete Appl. Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB5","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0166-218X(90)90001-S","article-title":"Recognizing tough graphs is NP-hard","volume":"28","author":"Bauer","year":"1990","journal-title":"Discrete Appl. Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB6","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0166-218X(99)00142-0","article-title":"Chordality and 2-factors in tough graphs","volume":"99","author":"Bauer","year":"2000","journal-title":"Discrete Appl. Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB7","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0012-365X(90)90055-M","article-title":"Long cycles in graphs with large degree sums","volume":"79","author":"Bauer","year":"1989","journal-title":"Discrete Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB8","article-title":"Toughness, minimum degree and spanning cubic subgraphs","author":"Bauer","year":"2000","journal-title":"Preprint"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB9","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1002\/jgt.3190180304","article-title":"Toughness minimum degree and the existence of 2-factors","volume":"18","author":"Bauer","year":"1994","journal-title":"J. Graph Theory"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB10","series-title":"Graph Theory, Combinatorics, and Applications - Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs","first-page":"113","article-title":"Some recent results on long cycles in tough graphs","author":"Bauer","year":"1991"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB11","series-title":"Graph Theory, Combinatorics, and Applications - Proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs","first-page":"19","article-title":"Cycles in tough graphs - updating the last four years","author":"Bauer","year":"1995"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB12","series-title":"The Proceedings of the Eighth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and Applications","first-page":"69","article-title":"Progress on tough graphs - another four years","author":"Bauer","year":"1999"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB13","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/S0166-218X(97)00030-9","article-title":"The complexity of recognizing tough cubic graphs","volume":"79","author":"Bauer","year":"1997","journal-title":"Discrete Appl. Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB14","first-page":"47","article-title":"The complexity of toughness in regular graphs","volume":"130","author":"Bauer","year":"1998","journal-title":"Congr. Numer"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB15","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1002\/(SICI)1097-0118(199912)32:4<405::AID-JGT8>3.0.CO;2-Z","article-title":"More than 1-tough chordal planar graphs are hamiltonian","volume":"32","author":"B\u00f6hme","year":"1999","journal-title":"J. Graph Theory"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB16","doi-asserted-by":"crossref","unstructured":"A. Brandst\u00e4dt, V.B. Le, and J.P. Spinrad, Graph classes: a survey, SIAM Monographs on Discrete Mathematics and Applications (SIAM, Philadelphia, PA, 1999).","DOI":"10.1137\/1.9780898719796"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB17","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1002\/(SICI)1097-0037(199905)33:3<233::AID-NET9>3.0.CO;2-A","article-title":"Various results on the toughness of graphs","volume":"33","author":"Broersma","year":"1999","journal-title":"NETWORKS"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB18","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/s003730050035","article-title":"(2,k)-factor-critical graphs and toughness","volume":"15","author":"Cai","year":"1999","journal-title":"Graphs and Combin"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB19","series-title":"Graphs and Digraphs","author":"Chartrand","year":"1996"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB20","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1002\/(SICI)1097-0037(199801)31:1<29::AID-NET4>3.0.CO;2-M","article-title":"Tough enough chordal graphs are hamiltonian","volume":"31","author":"Chen","year":"1998","journal-title":"NETWORKS"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB21","unstructured":"V. Chv\u00e1tal, Private communication."},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB22","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0012-365X(73)90138-6","article-title":"Tough graphs and hamiltonian circuits","volume":"5","author":"Chv\u00e1tal","year":"1973","journal-title":"Discrete Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB23","series-title":"The Traveling Salesman Problem, A Guided Tour of Combinatorial Optimization","first-page":"403","article-title":"Hamiltonian cycles","author":"Chv\u00e1tal","year":"1985"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB24","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0012-365X(72)90079-9","article-title":"A note on hamiltonian circuits","volume":"2","author":"Chv\u00e1tal","year":"1972","journal-title":"Discrete Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB25","first-page":"107","article-title":"Dominating cycles in series-parallel graphs","volume":"19a","author":"Colbourn","year":"1985","journal-title":"Ars Combinatoria"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB26","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/BF02579361","article-title":"On submodular function minimization","volume":"5","author":"Cunningham","year":"1985","journal-title":"Combinatorica"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB27","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0012-365X(95)00359-5","article-title":"1-Tough cocomparability graphs are hamiltonian","volume":"170","author":"Deogun","year":"1997","journal-title":"Discrete Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB28","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0012-365X(91)90099-N","article-title":"An upper bound on the shortness exponent of 1-tough maximal planar graphs","volume":"90","author":"Dillencourt","year":"1991","journal-title":"Discrete Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB29","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<125::AID-JGT1>3.0.CO;2-X","article-title":"Toughness, trees and k-walks","volume":"33","author":"Ellingham","year":"2000","journal-title":"J. Graph Theory"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB30","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/BF01788075","article-title":"Toughness and the existence of k-factors II","volume":"2","author":"Enomoto","year":"1986","journal-title":"Graphs and Combin"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB31","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0012-365X(98)00059-4","article-title":"Toughness and the existence of k-factors III","volume":"189","author":"Enomoto","year":"1998","journal-title":"Discrete Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB32","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1002\/jgt.3190090106","article-title":"Toughness and the existence of k-factors","volume":"9","author":"Enomoto","year":"1985","journal-title":"J. Graph Theory"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB33","unstructured":"R. Faudree, R. Gould, M. Jacobson, L. Lesniak, and A. Saito, Private communication."},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB34","doi-asserted-by":"crossref","first-page":"41","DOI":"10.7151\/dmgt.1022","article-title":"On k-factor-critical graphs","volume":"16","author":"Favaron","year":"1996","journal-title":"Discussiones Mathematicae - Graph Theory"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB35","unstructured":"K. Ferland, Toughness of generalized Petersen graphs, Preprint."},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB36","first-page":"65","article-title":"On the toughness of some generalized Petersen graphs","volume":"36","author":"Ferland","year":"1993","journal-title":"Ars Combinatoria"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB37","series-title":"Computers and Intractability","author":"Garey","year":"1979"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB38","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/S0012-365X(96)00238-5","article-title":"Maximum and minimum toughness of graphs of small genus","volume":"167\/168","author":"Goddard","year":"1997","journal-title":"Discrete Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB39","series-title":"Graph Theory, Combinatorics, and Applications - Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs","first-page":"535","article-title":"On some extremal problems in connectivity","author":"Goddard","year":"1991"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB40","series-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel","year":"1988"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB41","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1016\/0097-3165(73)90012-5","article-title":"Shortness exponents of families of graphs","volume":"14","author":"Gr\u00fcnbaum","year":"1973","journal-title":"J. Combinat. Theory - Ser. B"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB42","first-page":"145","article-title":"A characterization of 3\/2-tough cubic graphs","volume":"38","author":"Jackson","year":"1994","journal-title":"Ars Combinatoria"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB43","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/S0167-5060(08)70503-X","article-title":"On maximal circuits in finite graphs","volume":"3","author":"Jung","year":"1987","journal-title":"Ann. Discrete Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB44","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/S0012-365X(96)00051-9","article-title":"Toughness and edge-toughness","volume":"164","author":"Katona","year":"1997","journal-title":"Discrete Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB45","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/s003730050065","article-title":"Properties of edge-tough graphs","volume":"15","author":"Katona","year":"1999","journal-title":"Graphs and Combin"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB46","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","article-title":"Finding Hamiltonian circuits in interval graphs","volume":"20","author":"Kiel","year":"1985","journal-title":"Inf. Process. Lett"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB47","unstructured":"D. Kratsch, Private communication."},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB48","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0012-365X(95)00190-8","article-title":"Toughness hamiltonicity and split graphs","volume":"150","author":"Kratsch","year":"1996","journal-title":"Discrete Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB49","first-page":"355","article-title":"Cycles through many vertices of given subsets in 1-tough graphs","volume":"27","author":"Li","year":"1997","journal-title":"J. China Univ. Sci. Tech"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB50","first-page":"195","article-title":"Cycles containing many vertices of subsets in 1-tough graphs with large degree sums","volume":"48","author":"Li","year":"1998","journal-title":"Ars Combin"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB51","article-title":"k-factors and extendability with prescribed components","author":"Liu","year":"2000","journal-title":"Preprint"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB52","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1002\/jgt.3190080116","article-title":"Hamiltonian results in K1,3-free graphs","volume":"1","author":"Matthews","year":"1984","journal-title":"J. Graph Theory"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB53","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0012-365X(80)90240-X","article-title":"A 1-tough non hamiltonian maximal planar graph","volume":"30","author":"Nishizeki","year":"1980","journal-title":"Discrete Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB54","first-page":"289","article-title":"On the vulnerability of cycle permutation graphs","volume":"29","author":"Piazza","year":"1990","journal-title":"Ars Combinatoria"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB55","first-page":"179","article-title":"A note on toughness and tough components","volume":"125","author":"Plummer","year":"1997","journal-title":"Congr. Numer"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB56","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/0095-8956(79)90081-9","article-title":"Connectivity, genus and the number of components in vertex-deleted subgraphs","volume":"27","author":"Schmeichel","year":"1979","journal-title":"J. Combinat. Theory - Ser. B"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB57","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/s003730050053","article-title":"(3,k)-factor-critical graphs and toughness","volume":"15","author":"Shi","year":"1999","journal-title":"Graphs and Combin"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB58","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1112\/plms\/s3-42.2.231","article-title":"Long cycles in digraphs","volume":"42","author":"Thomassen","year":"1981","journal-title":"Proc. London Math. Soc"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB59","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0012-365X(94)00356-N","article-title":"On the shortness exponent of 1-tough maximal planar graphs","volume":"154","author":"Tk\u00e1\u010d","year":"1996","journal-title":"Discrete Math"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB60","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/S0021-9800(69)80116-X","article-title":"A theorem on Tait colorings with an application to the generalized Petersen graphs","volume":"6","author":"Watkins","year":"1969","journal-title":"J. Combin. Theory"},{"key":"10.1016\/S1571-0653(04)00055-1_NEWBIB61","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/S0012-365X(98)00156-3","article-title":"The toughness of split graphs","volume":"190","author":"Woeginger","year":"1998","journal-title":"Discrete Math"}],"container-title":["Electronic Notes in Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304000551?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304000551?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,2]],"date-time":"2019-02-02T21:54:51Z","timestamp":1549144491000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571065304000551"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,7]]},"references-count":61,"alternative-id":["S1571065304000551"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0653(04)00055-1","relation":{},"ISSN":["1571-0653"],"issn-type":[{"value":"1571-0653","type":"print"}],"subject":[],"published":{"date-parts":[[2002,7]]}}}