{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T05:35:47Z","timestamp":1774071347676,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2018,3,22]],"date-time":"2018-03-22T00:00:00Z","timestamp":1521676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"J\u00e1nos Bolyai Research Scholarship of the Hungarian Academy of Sciences"},{"DOI":"10.13039\/501100003549","name":"Hungarian Scientific Research Fund","doi-asserted-by":"crossref","award":["OTKA 108947"],"award-info":[{"award-number":["OTKA 108947"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2018,11,15]]},"abstract":"<jats:p>\n            It is known that the problem of deciding\n            <jats:italic>k<\/jats:italic>\n            -colorability of a graph exhibits an easy-hard-easy pattern,\u2014that is, the average-case complexity for backtrack-type algorithms, as a function of\n            <jats:italic>k<\/jats:italic>\n            , has a peak. This complexity peak is either at\n            <jats:italic>k<\/jats:italic>\n            = \u03c7 \u2212 1 or\n            <jats:italic>k<\/jats:italic>\n            = \u03c7, where \u03c7 is the chromatic number of the graph. However, the behavior around the complexity peak is poorly understood. In this article, we use list coloring to model coloring with a fractional number of colors between \u03c7 \u2212 1 and \u03c7. We present a comprehensive computational study on the complexity of backtrack-type graph coloring algorithms in this critical range. According to our findings, an easy-hard-easy pattern can be observed on a finer scale between \u03c7 \u2212 1 and \u03c7 as well. The highest complexity found this way can be higher than for any integer value of\n            <jats:italic>k<\/jats:italic>\n            . It turns out that the complexity follows an alternating three-dimensional pattern; understanding this pattern is very important for benchmarking purposes. Our results also answer the previously open question whether coloring with \u03c7 \u2212 1 or with \u03c7 colors is harder: this depends on the location of the maximal fractional complexity.\n          <\/jats:p>","DOI":"10.1145\/3183350","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T12:29:49Z","timestamp":1521808189000},"page":"1-19","source":"Crossref","is-referenced-by-count":5,"title":["Complexity of Coloring Random Graphs"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5741-2709","authenticated-orcid":false,"given":"Zolt\u00e1n \u00c1d\u00e1m","family":"Mann","sequence":"first","affiliation":[{"name":"University of Duisburg-Essen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2018,3,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.11"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796351"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00120-X"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007442"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215914"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2005.02.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1661445.1661509"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90044-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122551"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548303006060"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/359094.359101"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/177492.177575"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.19.4.456"},{"key":"e_1_2_1_14_1","series-title":"Lecture Notes in Computer Science","volume-title":"Programming Languages: Implementations, Logics, and Programs","author":"Carlsson Mats","unstructured":"Mats Carlsson , Greger Ottosson , and Bj\u00f6rn Carlson . 1997. An open-ended finite domain constraint solver . In Programming Languages: Implementations, Logics, and Programs . Lecture Notes in Computer Science , Vol. 1292 . Springer , 191--206. Mats Carlsson, Greger Ottosson, and Bj\u00f6rn Carlson. 1997. An open-ended finite domain constraint solver. In Programming Languages: Implementations, Logics, and Programs. Lecture Notes in Computer Science, Vol. 1292. Springer, 191--206."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI\u201991)","author":"Cheeseman Peter","unstructured":"Peter Cheeseman , Bob Kanefsky , and William M. Taylor . 1991. Where the really hard problems are . In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI\u201991) . 331--337. Peter Cheeseman, Bob Kanefsky, and William M. Taylor. 1991. Where the really hard problems are. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI\u201991). 331--337."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.86.1654"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00164-5"},{"key":"e_1_2_1_19_1","volume-title":"Academic Press","author":"de la Vega W. Fernandez","unstructured":"W. Fernandez de la Vega . 1984. On the chromatic number of sparse random graphs . In Graph Theory and Combinatorics, B. Bollob\u00e1s (Ed.). Academic Press , Cambridge , MA , 321--328. W. Fernandez de la Vega. 1984. On the chromatic number of sparse random graphs. In Graph Theory and Combinatorics, B. Bollob\u00e1s (Ed.). Academic Press, Cambridge, MA, 321--328."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/36\/43\/027"},{"key":"e_1_2_1_21_1","unstructured":"P\u00e1l Erd\u0151s and Alfr\u00e9d R\u00e9nyi. 1960. On the evolution of random graphs. Matematikai Kutat\u00f3 Int\u00e9zet K\u00f6zlem\u00e9nyei 5 17--61.  P\u00e1l Erd\u0151s and Alfr\u00e9d R\u00e9nyi. 1960. On the evolution of random graphs. Matematikai Kutat\u00f3 Int\u00e9zet K\u00f6zlem\u00e9nyei 5 17--61."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1006314320276"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100051124"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/944618.944628"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00044-5"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90088-4"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30201-8_58"},{"key":"e_1_2_1_30_1","volume-title":"Complexity of Computer Computations","author":"Karp Richard M.","unstructured":"Richard M. Karp . 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations , R. E. Miller and J. W. Thatcher (Eds.). Plenum , 85--103. Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (Eds.). Plenum, 85--103."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375472"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205080"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 13th International Multiconference, Information Society - IS","volume":"392","author":"Mann Zolt\u00e1n \u00c1d\u00e1m","year":"2010","unstructured":"Zolt\u00e1n \u00c1d\u00e1m Mann and Anik\u00f3 Szajk\u00f3 . 2010 . Determining the expected runtime of exact graph coloring . In Proceedings of the 13th International Multiconference, Information Society - IS , Volume A. 389-- 392 . Zolt\u00e1n \u00c1d\u00e1m Mann and Anik\u00f3 Szajk\u00f3. 2010. Determining the expected runtime of exact graph coloring. In Proceedings of the 13th International Multiconference, Information Society - IS, Volume A. 389--392."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SYNASC.2010.61"},{"key":"e_1_2_1_35_1","volume-title":"Optimization in Computer Engineering\u2014Theory and Applications","author":"Mann Zolt\u00e1n \u00c1d\u00e1m","unstructured":"Zolt\u00e1n \u00c1d\u00e1m Mann . 2011. Optimization in Computer Engineering\u2014Theory and Applications . Scientific Research Publishing , Wuhan, China . Zolt\u00e1n \u00c1d\u00e1m Mann. 2011. Optimization in Computer Engineering\u2014Theory and Applications. Scientific Research Publishing, Wuhan, China."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2013.04.018"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.06.003"},{"key":"e_1_2_1_38_1","volume-title":"Linear Programming\u2014New Frontiers in Theory and Applications, Z. \u00c1","author":"Mann Zolt\u00e1n \u00c1d\u00e1m","unstructured":"Zolt\u00e1n \u00c1d\u00e1m Mann and Anik\u00f3 Szajk\u00f3 . 2012. Complexity of different ILP models of the frequency assignment problem . In Linear Programming\u2014New Frontiers in Theory and Applications, Z. \u00c1 . Mann (Ed.). Nova Science , 305--326. Zolt\u00e1n \u00c1d\u00e1m Mann and Anik\u00f3 Szajk\u00f3. 2012. Complexity of different ILP models of the frequency assignment problem. In Linear Programming\u2014New Frontiers in Theory and Applications, Z. \u00c1. Mann (Ed.). Nova Science, 305--326."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"D. W. Matula G. Marble and J. D. Isaacson. 1972. Graph coloring algorithms. In Graph Theory and Computing R. C. Read (Ed.). Academic Press 109--122.  D. W. Matula G. Marble and J. D. Isaacson. 1972. Graph coloring algorithms. In Graph Theory and Computing R. C. Read (Ed.). Academic Press 109--122.","DOI":"10.1016\/B978-1-4832-3187-7.50015-5"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/inte.11.5.57"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214060"},{"key":"e_1_2_1_42_1","volume-title":"On the analysis of backtrack procedures for the coloring of random graphs","author":"Monasson R\u00e9mi","unstructured":"R\u00e9mi Monasson . 2004. On the analysis of backtrack procedures for the coloring of random graphs . In Complex Networks, E. Ben-Naim, H. Frauenfelder, and Z. Toroczkai (Eds.). Springer , 235--254. R\u00e9mi Monasson. 2004. On the analysis of backtrack procedures for the coloring of random graphs. In Complex Networks, E. Ben-Naim, H. Frauenfelder, and Z. Toroczkai (Eds.). Springer, 235--254."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_34"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1038\/22055"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.09.019"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00045-3"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579208"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90003-8"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/CINTI.2010.5672261"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90005-3"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 18th National Conference on Artificial Intelligence. 695--700","author":"Walsh Toby","year":"2002","unstructured":"Toby Walsh . 2002 . The interface between P and NP: COL, XOR, NAE, 1-in-k, and Horn SAT . In Proceedings of the 18th National Conference on Artificial Intelligence. 695--700 . Toby Walsh. 2002. The interface between P and NP: COL, XOR, NAE, 1-in-k, and Horn SAT. In Proceedings of the 18th National Conference on Artificial Intelligence. 695--700."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90013-9"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence. 1173--1178","author":"Williams Ryan","year":"2003","unstructured":"Ryan Williams , Carla P. Gomes , and Bart Selman . 2003 . Backdoors to typical case complexity . In Proceedings of the 18th International Joint Conference on Artificial Intelligence. 1173--1178 . Ryan Williams, Carla P. Gomes, and Bart Selman. 2003. Backdoors to typical case complexity. In Proceedings of the 18th International Joint Conference on Artificial Intelligence. 1173--1178."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3183350","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3183350","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:13Z","timestamp":1750210753000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3183350"}},"subtitle":["An Experimental Study of the Hardest Region"],"short-title":[],"issued":{"date-parts":[[2018,3,22]]},"references-count":54,"alternative-id":["10.1145\/3183350"],"URL":"https:\/\/doi.org\/10.1145\/3183350","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,22]]}}}