{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T12:08:39Z","timestamp":1768651719790,"version":"3.49.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,21]],"date-time":"2014-10-21T00:00:00Z","timestamp":1413849600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9949-6","type":"journal-article","created":{"date-parts":[[2014,10,20]],"date-time":"2014-10-20T16:33:16Z","timestamp":1413822796000},"page":"385-414","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Algorithms and Almost Tight Results for $$3$$ 3 -Colorability of Small Diameter Graphs"],"prefix":"10.1007","volume":"74","author":[{"given":"George B.","family":"Mertzios","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,21]]},"reference":[{"key":"9949_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01787474","volume":"6","author":"N Alon","year":"1990","unstructured":"Alon, N.: Transversal numbers of uniform hypergraphs. Graphs Comb. 6, 1\u20134 (1990)","journal-title":"Graphs Comb."},{"key":"9949_CR2","doi-asserted-by":"crossref","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 3rd edn. Wiley, London (2008)","edition":"3"},{"key":"9949_CR3","first-page":"3","volume":"11","author":"V Arnautov","year":"1974","unstructured":"Arnautov, V.: Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices. Prikl. Mat. i Programmirovanie 11, 3\u20138 (1974)","journal-title":"Prikl. Mat. i Programmirovanie"},{"key":"9949_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L., Luks, E. M.: Canonical labeling of graphs. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC), pp. 171\u2013183 (1983)","DOI":"10.1145\/800061.808746"},{"issue":"2","key":"9949_CR5","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/j.jalgor.2004.06.008","volume":"54","author":"R Beigel","year":"2005","unstructured":"Beigel, R., Eppstein, D.: $$3$$ 3 -Coloring in time $${O}(1.3289^{n})$$ O ( 1 . 3289 n ) . J. Algorithms 54(2), 168\u2013204 (2005)","journal-title":"J. Algorithms"},{"issue":"12","key":"9949_CR6","doi-asserted-by":"crossref","first-page":"1680","DOI":"10.1016\/j.dam.2012.03.029","volume":"160","author":"M Bodirsky","year":"2012","unstructured":"Bodirsky, M., K\u00e1ra, J., Martin, B.: The complexity of surjective homomorphism problems\u2014a survey. Discrete Appl. Math. 160(12), 1680\u20131690 (2012)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9949_CR7","doi-asserted-by":"crossref","first-page":"41","DOI":"10.2307\/1998567","volume":"267","author":"B Bollob\u00e1s","year":"1981","unstructured":"Bollob\u00e1s, B.: The diameter of random graphs. Trans. Am. Math. Soc. 267(1), 41\u201352 (1981)","journal-title":"Trans. Am. Math. Soc."},{"key":"9949_CR8","doi-asserted-by":"crossref","unstructured":"Broersma, H., Fomin, F. V., Golovach, P. A., Paulusma, D.: Three complexity results on coloring $${P}_{k}$$ P k -free graphs. In: Proceedings of the 20th International Workshop on Combinatorial Algorithms (IWOCA), pp. 95\u2013104 (2009)","DOI":"10.1007\/978-3-642-10217-2_12"},{"issue":"1","key":"9949_CR9","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"issue":"2\u20133","key":"9949_CR10","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0304-3975(86)90184-2","volume":"43","author":"K Edwards","year":"1986","unstructured":"Edwards, K.: The complexity of colouring problems on dense graphs. Theor. Comput. Sci. 43(2\u20133), 337\u2013343 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"9949_CR11","volume-title":"Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2010)"},{"key":"9949_CR12","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)"},{"key":"9949_CR13","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/S0304-0208(08)72943-8","volume":"88","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. Top. Perfect Graphs 88, 325\u2013356 (1984)","journal-title":"Top. Perfect Graphs"},{"issue":"1","key":"9949_CR14","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/s00453-008-9197-8","volume":"57","author":"CT Ho\u00e0ng","year":"2010","unstructured":"Ho\u00e0ng, C.T., Kami\u0144ski, M., Lozin, V.V., Sawada, J., Shu, X.: Deciding $$k$$ k -colorability of $${P}_{5}$$ P 5 -free graphs in polynomial time. Algorithmica 57(1), 74\u201381 (2010)","journal-title":"Algorithmica"},{"key":"9949_CR15","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10, 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9949_CR16","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$ k -SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9949_CR17","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9949_CR18","unstructured":"Kami\u0144ski, M.: Open problems from algorithmic graph theory. In: 7th Slovenian International Conference on Graph Theory (2011). http:\/\/rutcor.rutgers.edu\/mkaminski\/AGT\/openproblemsAGT"},{"key":"9949_CR19","first-page":"41","volume":"84","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 84, 41\u201371 (2011)","journal-title":"Bull. EATCS"},{"key":"9949_CR20","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/S0012-365X(97)89267-9","volume":"162","author":"F Maffray","year":"1996","unstructured":"Maffray, F., Preissmann, M.: On the NP-completeness of the $$k$$ k -colorability problem for triangle-free graphs. Discrete Math. 162, 313\u2013317 (1996)","journal-title":"Discrete Math."},{"key":"9949_CR21","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/j.ipl.2010.11.009","volume":"111","author":"N Narayanaswamy","year":"2011","unstructured":"Narayanaswamy, N., Subramanian, C.: Dominating set based exact algorithms for 3-coloring. Inf. Proces. Lett. 111, 251\u2013255 (2011)","journal-title":"Inf. Proces. Lett."},{"key":"9949_CR22","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"9949_CR23","first-page":"307","volume":"17","author":"C Payan","year":"1975","unstructured":"Payan, C.: Sur le nombre d\u2019absorption d\u2019un graphe simple. Cahiers Centre \u00c9tudes Recherche Op\u00e9r 17, 307\u2013317 (1975)","journal-title":"Cahiers Centre \u00c9tudes Recherche Op\u00e9r"},{"issue":"2\u20133","key":"9949_CR24","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/S0166-218X(03)00446-3","volume":"136","author":"B Randerath","year":"2004","unstructured":"Randerath, B., Schiermeyer, I.: 3-Colorability $$\\in {P}$$ \u2208 P for $${P}_{6}$$ P 6 -free graphs. Discrete Appl. Math. 136(2\u20133), 299\u2013313 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9949_CR25","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1007\/s00453-012-9624-8","volume":"64","author":"J Stacho","year":"2012","unstructured":"Stacho, J.: 3-Colouring AT-free graphs in polynomial time. Algorithmica 64(3), 384\u2013399 (2012)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9949-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9949-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9949-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,26]],"date-time":"2019-02-26T14:15:49Z","timestamp":1551190549000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9949-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,21]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9949"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9949-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,21]]}}}