{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T08:48:36Z","timestamp":1676018916586},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,5,11]],"date-time":"2012-05-11T00:00:00Z","timestamp":1336694400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,5]]},"DOI":"10.1007\/s00224-012-9410-7","type":"journal-article","created":{"date-parts":[[2012,5,10]],"date-time":"2012-05-10T12:18:14Z","timestamp":1336652294000},"page":"645-667","source":"Crossref","is-referenced-by-count":2,"title":["Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds"],"prefix":"10.1007","volume":"52","author":[{"given":"Jean-Francois","family":"Couturier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Liedloff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Artem","family":"Pyatkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,5,11]]},"reference":[{"key":"9410_CR1","volume":"15","author":"N. Alon","year":"2008","unstructured":"Alon, N., Friedland, S.: The maximum number of perfect matchings in graphs with a given degree sequence. Electron. J. Comb. 15, N13 (2008)","journal-title":"Electron. J. Comb."},{"key":"9410_CR2","volume":"5","author":"N. Alon","year":"1998","unstructured":"Alon, N., R\u00f6dl, V., Rucinski, A.: Perfect matchings in \u03f5-regular graphs. Electron. J. Comb. 5, R13 (1998)","journal-title":"Electron. J. Comb."},{"key":"9410_CR3","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-coloring in time O(1.3289 n ). J. Algorithms 54, 168\u2013204 (2005)","journal-title":"J. Algorithms"},{"key":"9410_CR4","author":"S. Bessy","year":"2012","unstructured":"Bessy, S., Havet, F.: Enumerating the edge-colourings and total colourings of a regular graph. J. Comb. Optim. (2012). doi: 10.1007\/s10878-011-9448-5","journal-title":"J. Comb. Optim."},{"key":"9410_CR5","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1109\/FOCS.2006.41","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006)","author":"A. Bj\u00f6rklund","year":"2006","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Inclusion\u2013exclusion algorithms for counting set partitions. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp.\u00a0575\u2013582. IEEE, New York (2006)"},{"key":"9410_CR6","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"H.L. Bodlaender","year":"1990","unstructured":"Bodlaender, H.L.: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. J. Algorithms 11, 631\u2013643 (1990)","journal-title":"J. Algorithms"},{"key":"9410_CR7","first-page":"945","volume":"14","author":"L.M. Bregman","year":"1973","unstructured":"Bregman, L.M.: Some properties of nonnegative matrices and their permanents. Sov. Math. Dokl. 14, 945\u2013949 (1973)","journal-title":"Sov. Math. Dokl."},{"key":"9410_CR8","first-page":"329","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"D. Eppstein","year":"2001","unstructured":"Eppstein, D.: Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 329\u2013337. SIAM, Philadelphia (2001)"},{"key":"9410_CR9","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0166-218X(00)00387-5","volume":"113","author":"J. Fiala","year":"2001","unstructured":"Fiala, J., Kloks, T., Kratochv\u00edl, J.: Fixed-parameter complexity of lambda-labelings. Discrete Appl. Math. 113, 59\u201372 (2001)","journal-title":"Discrete Appl. Math."},{"key":"9410_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/978-3-540-73545-8_9","volume-title":"COCOON 2007","author":"F.V. Fomin","year":"2007","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S.: Improved exact algorithms for counting 3- and 4-colorings. In: COCOON 2007. Lecture Notes in Computer Science, vol. 4598, pp. 65\u201374. Springer, Berlin (2007)"},{"key":"9410_CR11","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"F.V. Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S.: On two techniques of combining branching and treewidth. Algorithmica 54, 181\u2013207 (2009)","journal-title":"Algorithmica"},{"key":"9410_CR12","first-page":"47","volume":"87","author":"F. Fomin","year":"2005","unstructured":"Fomin, F., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. Bull. Eur. Assoc. Theor. Comput. Sci. 87, 47\u201377 (2005)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"issue":"1","key":"9410_CR13","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1145\/1435375.1435384","volume":"5","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Grandoni, F., Pyatkin, A., Stepanov, A.: Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Trans. Algorithms 5(1), 9 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"9410_CR14","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.ipl.2005.10.012","volume":"97","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., H\u00f8ie, K.: Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett. 97, 191\u2013196 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9410_CR15","volume-title":"Texts in Theoretical Computer Science","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact exponential algorithms. In: Texts in Theoretical Computer Science. Springer, Berlin (2010)"},{"key":"9410_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York (1979)"},{"key":"9410_CR17","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1007\/s00453-010-9474-1","volume":"62","author":"S. Gaspers","year":"2012","unstructured":"Gaspers, S., Kratsch, D., Liedloff, M.: On independent sets and bicliques in graphs. Algorithmica 62, 637\u2013658 (2012)","journal-title":"Algorithmica"},{"key":"9410_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/978-3-642-16926-7_6","volume-title":"Proceedings of the 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2010)","author":"P.A. Golovach","year":"2010","unstructured":"Golovach, P.A., Kratsch, D., Couturier, J.F.: Colorings with few colors: counting, enumeration and combinatorial bounds. In: Thilikos, D. (ed.) Proceedings of the 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2010). Lecture Notes in Computer Science, vol. 6410, pp. 39\u201350. Springer, Berlin (2010)"},{"key":"9410_CR19","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/s00453-009-9302-7","volume":"59","author":"F. Havet","year":"2011","unstructured":"Havet, F., Klazar, M., Kratochv\u00edl, J., Kratsch, D., Liedloff, M.: Exact algorithms for L(2,1)-labeling of graphs. Algorithmica 59, 169\u2013194 (2011)","journal-title":"Algorithmica"},{"key":"9410_CR20","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."},{"key":"9410_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/978-3-642-20877-5_9","volume-title":"Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011)","author":"K. Junosza-Szaniawski","year":"2011","unstructured":"Junosza-Szaniawski, K., Kratochv\u00edl, J., Liedloff, M., Rossmanith, P., Rzazewski, P.: Fast exact algorithm for L(2,1)-labeling of graphs. In: Ogihara, M., Tarui, J. (eds.) Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011). Lecture Notes in Computer Science, vol. 6648, pp. 82\u201393. Springer, Berlin (2011)"},{"key":"9410_CR22","series-title":"Lecture Notes in Computer Science","first-page":"34","volume-title":"Proceedings of the 21st International Workshop on Combinatorial Algorithms (IWOCA 2010)","author":"K. Junosza-Szaniawski","year":"2010","unstructured":"Junosza-Szaniawski, K., Rzazewski, P.: On improved exact algorithms for L(2,1)-labeling of graphs. In: Iliopoulos, C.S., Smyth, W.F. (eds.) Proceedings of the 21st International Workshop on Combinatorial Algorithms (IWOCA 2010). Lecture Notes in Computer Science, vol. 6460, pp. 34\u201337. Springer, Berlin (2010)"},{"key":"9410_CR23","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1016\/j.ipl.2011.04.010","volume":"111","author":"K. Junosza-Szaniawski","year":"2011","unstructured":"Junosza-Szaniawski, K., Rzazewski, P.: On the complexity of exact algorithm for L(2,1)-labeling of graphs. Inf. Process. Lett. 111, 697\u2013701 (2011)","journal-title":"Inf. Process. Lett."},{"key":"9410_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth, Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. Lecture Notes in Computer Science, vol. 842. Springer, Berlin (1994)"},{"key":"9410_CR25","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1109\/FOCS.2006.11","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006)","author":"M. Koivisto","year":"2006","unstructured":"Koivisto, M.: An O(2 n ) algorithm for graph coloring and other partitioning problems via inclusion-exclusion. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 583\u2013590. IEEE, New York (2006)"},{"key":"9410_CR26","doi-asserted-by":"crossref","first-page":"3733","DOI":"10.1016\/j.tcs.2009.05.005","volume":"410","author":"L. Kowalik","year":"2009","unstructured":"Kowalik, L.: Improved edge-coloring with three colors. Theor. Comput. Sci. 410, 3733\u20133742 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9410_CR27","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1016\/j.dam.2004.01.020","volume":"145","author":"D. Kr\u00e1l","year":"2005","unstructured":"Kr\u00e1l, D.: An exact algorithm for the channel assignment problem. Discrete Appl. Math. 145, 326\u2013331 (2005)","journal-title":"Discrete Appl. Math."},{"key":"9410_CR28","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"J.W. Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 3, 23\u201328 (1965)","journal-title":"Isr. J. Math."},{"key":"9410_CR29","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/BF02771690","volume":"9","author":"M. Rosenfeld","year":"1971","unstructured":"Rosenfeld, M.: On the total coloring of certain graphs. Isr. J. Math. 9, 396\u2013402 (1971)","journal-title":"Isr. J. Math."},{"key":"9410_CR30","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0012-365X(89)90187-8","volume":"78","author":"A. S\u00e1nchez-Arroyo","year":"1989","unstructured":"S\u00e1nchez-Arroyo, A.: Determining the total colouring number is NP-hard. Discrete Math. 78, 315\u2013319 (1989)","journal-title":"Discrete Math."},{"key":"9410_CR31","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1006\/eujc.1999.0440","volume":"23","author":"C. Szegedy","year":"2002","unstructured":"Szegedy, C.: On the number of 3-edge colorings of cubic graphs. Eur. J. Comb. 23, 113\u2013120 (2002)","journal-title":"Eur. J. Comb."},{"key":"9410_CR32","first-page":"25","volume":"3","author":"V.G. Vizing","year":"1964","unstructured":"Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Diskretn. Anal. 3, 25\u201330 (1964) (in Russian)","journal-title":"Diskretn. Anal."},{"key":"9410_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization\u2014Eureka, You Shrink!","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Combinatorial Optimization\u2014Eureka, You Shrink! Lecture Notes in Computer Science, vol. 2570, pp. 185\u2013207. Springer, Berlin (2003)"},{"key":"9410_CR34","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1109\/ISPAN.1994.367150","volume-title":"Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks","author":"X. Zhou","year":"1994","unstructured":"Zhou, X., Nishizeki, T.: Optimal parallel algorithm for edge-coloring partial k-trees with bounded degrees. In: Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, pp. 167\u2013174. IEEE, New York (1994)"},{"key":"9410_CR35","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1006\/jagm.1996.0061","volume":"21","author":"X. Zhou","year":"1996","unstructured":"Zhou, X., Nakano, S., Nishizeki, T.: Edge-coloring partial k-trees. J. Algorithms 21, 598\u2013617 (1996)","journal-title":"J. Algorithms"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9410-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-012-9410-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9410-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:24Z","timestamp":1558698864000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-012-9410-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,11]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["9410"],"URL":"https:\/\/doi.org\/10.1007\/s00224-012-9410-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,11]]}}}