{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:55:29Z","timestamp":1725569729982},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642169250"},{"type":"electronic","value":"9783642169267"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16926-7_6","type":"book-chapter","created":{"date-parts":[[2010,11,10]],"date-time":"2010-11-10T02:48:26Z","timestamp":1289357306000},"page":"39-50","source":"Crossref","is-referenced-by-count":2,"title":["Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds"],"prefix":"10.1007","author":[{"given":"Petr A.","family":"Golovach","sequence":"first","affiliation":[]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[]},{"given":"Jean-Francois","family":"Couturier","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"publisher","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                    n\n                  ). Journal of Algorithms\u00a054, 168\u2013204 (2005)","journal-title":"Journal of Algorithms"},{"key":"6_CR2","doi-asserted-by":"publisher","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-exclusion algorithms for counting set partitions. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 575\u2013582. IEEE, Los Alamitos (2006)"},{"key":"6_CR3","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings, arXiv:1007.1161v1 (2010)"},{"key":"6_CR4","doi-asserted-by":"publisher","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\u00a011, 631\u2013643 (1990)","journal-title":"J. Algorithms"},{"key":"6_CR5","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":"6_CR6","doi-asserted-by":"publisher","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 Applied Mathematics\u00a0113, 59\u201372 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-540-73545-8_9","volume-title":"Computing and Combinatorics","author":"F.V. Fomin","year":"2007","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S.: Improved exact algorithms for counting 3- and 4-colorings. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 65\u201374. Springer, Heidelberg (2007)"},{"key":"6_CR8","doi-asserted-by":"publisher","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\u00a054, 181\u2013207 (2009)","journal-title":"Algorithmica"},{"key":"6_CR9","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. Bulletin of the EATCS\u00a087, 47\u201377 (2005)","journal-title":"Bulletin of the EATCS"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Pyatkin, A., Stepanov, A.: Combinatorial bounds via Measure and Conquer: Bounding minimal dominating sets and applications. ACM Transactions on Algorithms\u00a05(1), Article 9 (2008)","DOI":"10.1145\/1435375.1435384"},{"key":"6_CR11","doi-asserted-by":"publisher","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.\u00a097, 191\u2013196 (2006)","journal-title":"Inf. Process. Lett."},{"key":"6_CR12","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":"6_CR13","doi-asserted-by":"publisher","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.\u00a010, 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"6_CR14","doi-asserted-by":"publisher","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                    n\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), 2nd edn., pp. 583\u2013590. IEEE, Los Alamitos (2006)","edition":"2"},{"key":"6_CR15","doi-asserted-by":"publisher","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. Theoret. Comp. Sci.\u00a0410, 3733\u20133742 (2009)","journal-title":"Theoret. Comp. Sci."},{"key":"6_CR16","doi-asserted-by":"publisher","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 Applied Mathematics\u00a0145, 326\u2013331 (2005)","journal-title":"Discrete Applied Mathematics"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/978-3-540-74456-6_46","volume-title":"Mathematical Foundations of Computer Science 2007","author":"J. Kratochv\u00edl","year":"2007","unstructured":"Kratochv\u00edl, J., Kratsch, D., Liedloff, M.: Exact algorithms for L(2,1)-labeling of graphs. In: Kucera, L., Kucera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 513\u2013524. Springer, Heidelberg (2007)"},{"key":"6_CR18","doi-asserted-by":"publisher","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. Israel J. Math.\u00a03, 23\u201328 (1965)","journal-title":"Israel J. Math."},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/BF02771690","volume":"9","author":"M. Rosenfeld","year":"1971","unstructured":"Rosenfeld, M.: On the total coloring of certain graphs. Israel Journal of Mathematics\u00a09, 396\u2013402 (1971)","journal-title":"Israel Journal of Mathematics"},{"key":"6_CR20","doi-asserted-by":"publisher","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 Mathematics\u00a078, 315\u2013319 (1989)","journal-title":"Discrete Mathematics"},{"key":"6_CR21","unstructured":"Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Diskret. Anal., 25\u201330 (1964) (in Russian)"},{"key":"6_CR22","doi-asserted-by":"publisher","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, Los Alamitos (1994)"},{"key":"6_CR23","doi-asserted-by":"publisher","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\u00a021, 598\u2013617 (1996)","journal-title":"J. Algorithms"}],"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\/978-3-642-16926-7_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,22]],"date-time":"2019-03-22T00:16:30Z","timestamp":1553213790000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16926-7_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642169250","9783642169267"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16926-7_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}