{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:12:55Z","timestamp":1725455575652},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540637578"},{"type":"electronic","value":"9783540696438"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0024491","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T02:30:56Z","timestamp":1132367456000},"page":"100-108","source":"Crossref","is-referenced-by-count":1,"title":["Computing the independence number of dense triangle-free graphs"],"prefix":"10.1007","author":[{"given":"Stephan","family":"Brandt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, D. Karger and M. Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, in: Proc. 27th ACM Symp. on Theory of Computing, 1995, pp. 284\u2013293.","DOI":"10.1145\/225058.225140"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof verification and hardness of approximation problems, in: Proc. IEEE Foundations of Computer Science, 1992, pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"10_CR3","first-page":"399","volume-title":"Approximation algorithms for NP-hard problems","author":"S. Arora","year":"1995","unstructured":"S. Arora and C. Lund, Hardness of approximations, in: Approximation algorithms for NP-hard problems (D. S. Hochbaum, ed.), PWS, Boston, 1995, pp. 399\u2013446."},{"key":"10_CR4","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1006\/jctb.1995.1051","volume":"65","author":"D. Bauer","year":"1995","unstructured":"D. Bauer, J. van den Heuvel and E. Schmeichel, Toughness and triangle-free graphs, J. Combin. Theory Ser. B65, (1995), 208\u2013221.","journal-title":"J. Combin. Theory Ser. B"},{"key":"10_CR5","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0012-365X(76)90078-9","volume":"15","author":"J. A. Bondy","year":"1976","unstructured":"J. A. Bondy and V. Chv\u00e1tal, A method in graph theory, Discrete Math.15 (1976), 111\u2013135.","journal-title":"Discrete Math."},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"S. Brandt, Cycles and paths in triangle-free graphs, in: The Mathematics of Paul Erd\u00f6s (R. L. Graham and J. Ne\u0161e\u0165ril, eds.), Springer, 1996, pp. 32\u201342.","DOI":"10.1007\/978-3-642-60406-5_4"},{"key":"10_CR7","unstructured":"S. Brandt, On the structure of dense triangle-free graphs, submitted."},{"key":"10_CR8","unstructured":"S. Brandt, Triangle-free graphs whose independence number equals the degree, manuscript."},{"key":"10_CR9","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput.9 (1990), 251\u2013280.","journal-title":"J. Symbolic Comput."},{"issue":"3","key":"10_CR10","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1112\/plms\/s3-2.1.69","volume":"2","author":"G. A. Dirac","year":"1952","unstructured":"G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. (3) 2 (1952), 69\u201381.","journal-title":"Proc. London Math. Soc."},{"key":"10_CR11","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/0012-365X(73)90126-X","volume":"5","author":"P. Erd\u00f6s","year":"1972","unstructured":"P. Erd\u00f6s and M. Simonovits, On a valence problem in extremal graph theory, Discrete Math.5 (1972), 323\u2013334.","journal-title":"Discrete Math."},{"key":"10_CR12","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0304-3975(86)90184-2","volume":"43","author":"K. Edwards","year":"1986","unstructured":"K. Edwards, The complexity of colouring problems on dense graphs, Theoretical Camp. Sci.43 (1986), 337\u2013343.","journal-title":"Theoretical Camp. Sci."},{"key":"10_CR13","volume-title":"Computers and intractability: a guide to NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and intractability: a guide to NP-completeness, W. H. Freeman, New York, 1979."},{"key":"10_CR14","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1017\/S0963548300000055","volume":"1","author":"R. H\u00e4ggkvist","year":"1992","unstructured":"R. H\u00e4ggkvist, On the structure of non-hamiltonian graphs I, Comb., Prob. and Comp.1 (1992), 27\u201334.","journal-title":"Comb., Prob. and Comp."},{"key":"10_CR15","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1017\/S0963548300000845","volume":"2","author":"G. Jin","year":"1993","unstructured":"G. Jin, Triangle-free graphs with high minimal degrees, Comb. Prob. and Comp.2, (1993), 479\u2013490.","journal-title":"Comb. Prob. and Comp."},{"key":"10_CR16","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0012-365X(94)00063-O","volume":"145","author":"G. Jin","year":"1995","unstructured":"G. Jin, Triangle-free four-chromatic graphs, Discrete Math.145 (1995), 151\u2013170.","journal-title":"Discrete Math."},{"key":"10_CR17","first-page":"17","volume-title":"Proc. 21st Ann. Symp. on Foundations of Computer Sc.","author":"S. Micali","year":"1980","unstructured":"S. Micali and V. V. Vazirani, An O(V1\/2E) algorithm for finding maximum matching in general graphs, Proc. 21st Ann. Symp. on Foundations of Computer Sc. IEEE, New York (1980), 17\u201327."},{"key":"10_CR18","first-page":"415","volume":"26","author":"J. Ne\u0161et\u0159il","year":"1985","unstructured":"J. Ne\u0161et\u0159il and S. Poljak, On the complexity of the subgraph problem, Comment. Math. Univ. Carolin.26 (1985), 415\u2013419.","journal-title":"Comment. Math. Univ. Carolin."},{"key":"10_CR19","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0012-365X(81)90221-1","volume":"37","author":"J. Pach","year":"1981","unstructured":"J. Pach, Graphs whose every independent set has a common neighbour, Discrete Math.37 (1981), 217\u2013228.","journal-title":"Discrete Math."},{"key":"10_CR20","first-page":"307","volume":"15","author":"S. Poljak","year":"1974","unstructured":"S. Poljak, A note on stable sets and colorings of graphs, Comment. Math. Univ. Carolinae15 (1974), 307\u2013309.","journal-title":"Comment. Math. Univ. Carolinae"},{"key":"10_CR21","unstructured":"Z. Ryj\u00e1\u010dek, On a closure concept in claw-free graphs, to appear in J. Combin. Theory Ser. B."},{"key":"10_CR22","unstructured":"H. J. Veldman, Personal communication, 1994."},{"key":"10_CR23","unstructured":"D. B. West, Introduction to graph theory, Prentice Hall, 1996."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0024491","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T21:35:22Z","timestamp":1586554522000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0024491"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540637578","9783540696438"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/bfb0024491","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}