An Algorithmic Framework for Colouring Locally Sparse Graphs
by Ewan Davies, Ross J. Kang, François Pirot, and Jean-Sébastien Sereni
Theory of Computing, Volume 22(2091), pp. 1-38, 2026
Bibliography with links to cited articles
[1] Dimitris Achlioptas and Amin Coja-Oghlan: Algorithmic barriers from phase transitions. In Proc. 49th FOCS, pp. 793–802. IEEE Comp. Soc., 2008. [doi:10.1109/FOCS.2008.11]
[2] Dimitris Achlioptas, Fotis Iliopoulos, and Alistair Sinclair: Beyond the Lovász Local Lemma: Point to set correlations and their algorithmic applications. In Proc. 60th FOCS, pp. 725–744. IEEE Comp. Soc., 2019. [doi:10.1109/FOCS.2019.00049]
[3] Miklós Ajtai, János Komlós, and Endre Szemerédi: A note on Ramsey numbers. J. Combin. Theory–A, 29(3):354–360, 1980. [doi:10.1016/0097-3165(80)90030-8]
[4] Miklós Ajtai, János Komlós, and Endre Szemerédi: A dense infinite Sidon sequence. Europ. J. Combinat., 2(1):1–11, 1981. [doi:10.1016/S0195-6698(81)80014-5]
[5] Noga Alon: Independence numbers of locally sparse graphs and a Ramsey type problem. Random Struct. Algor., 9(3):271–278, 1996. [doi:10.1002/(SICI)1098-2418(199610)9:3¡271::AID-RSA1¿3.0.CO;2-U]
[6] Noga Alon, Michael Krivelevich, and Benny Sudakov: Coloring graphs with sparse neighborhoods. J. Combin. Theory–B, 77(1):73–82, 1999. [doi:10.1006/jctb.1999.1910]
[7] Nikhil Bansal, Anupam Gupta, and Guru Guruganesh: On the Lovász theta function for independent sets in sparse graphs. SIAM J. Comput., 47(3):1039–1055, 2018. Preliminary version in STOC’15. [doi:10.1137/15M1051002]
[8] Anton Bernshteyn: The Johansson–Molloy theorem for DP-coloring. Random Struct. Algor., 54(4):653–664, 2019. [doi:10.1002/rsa.20811]
[9] Hans L. Bodlaender: On linear time minor tests with depth-first search. J. Algorithms, 14(1):1–23, 1993. [doi:10.1006/jagm.1993.1001]
[10] Tom Bohman: The triangle-free process. Adv. Math., 221(5):1653–1677, 2009. [doi:10.1016/j.aim.2009.02.018]
[11] Tom Bohman and Peter Keevash: Dynamic concentration of the triangle-free process. Random Struct. Algor., 58(2):221–293, 2021. [doi:10.1002/rsa.20973]
[12] Marthe Bonamy, Tom Kelly, Peter Nelson, and Luke Postle: Bounding χ by a fraction of Δ for graphs without large cliques. J. Combin. Theory–B, 157:263–282, 2022. [doi:10.1016/j.jctb.2022.06.002]
[13] Rob M. Corless, Gaston H. Gonnet, David E. G. Hare, David J. Jeffrey, and Donald E. Knuth: On the Lambert W function. Adv. Comput. Math., 5(1):329–359, 1996. [doi:10.1007/BF02124750]
[14] Ewan Davies, Rémi de Joannis de Verclos, Ross J. Kang, and François Pirot: Coloring triangle-free graphs with local list sizes. Random Struct. Algor., 57(3):730–744, 2020. [doi:10.1002/rsa.20945]
[15] Ewan Davies, Rémi de Joannis de Verclos, Ross J. Kang, and François Pirot: Occupancy fraction, fractional colouring, and triangle fraction. J. Graph Theory, 97(4):557–568, 2021. [doi:10.1002/jgt.22671]
[16] Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts: Independent sets, matchings, and occupancy fractions. J. London Math. Soc., 96(1):47–66, 2017. [doi:10.1112/jlms.12056]
[17] Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts: On the average size of independent sets in triangle-free graphs. Proc. AMS, 146(1):111–124, 2018. [doi:10.1090/proc/13728]
[18] Ewan Davies, Ross J. Kang, François Pirot, and Jean-Sébastien Sereni: Graph structure via local occupancy. 2020. [arXiv:2003.14361]
[19] Zdeněk Dvořák and Luke Postle: Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8. J. Combin. Theory–B, 129:38–54, 2018. [doi:10.1016/j.jctb.2017.09.001]
[20] Paul Erdős: Some remarks on the theory of graphs. Bull. AMS, 53(4):292–294, 1947. [doi:10.1090/S0002-9904-1947-08785-1]
[21] Paul Erdős: Graph theory and probability. Canad. J. Math., 11:34–38, 1959. [doi:10.4153/CJM-1959-003-9]
[22] Paul Erdős and Tibor Gallai: On maximal paths and circuits of graphs. Acta Math. Hungar., 10(3–4):337–356, 1959. [doi:10.1007/BF02024498]
[23] Paul Erdős and George Szekeres: A combinatorial problem in geometry. Compositio Math., 2:463–470, 1935. Available at EuDML.
[24] Paul Erdős and László Lovász: Problems and results on 3-chromatic hypergraphs and some related questions. In András Hajnal, Richard Rado, and Vera T. Sós, editors, Infinite and finite sets: To Paul Erdős on his 60th birthday, volume II of Colloq. Math. Soc. János Bolyai, 10, pp. 609–627. János Bolyai Math. Soc. and North-Holland, 1975.
[25] Louis Esperet and Aline Parreau: Acyclic edge-coloring using entropy compression. Europ. J. Combinat., 34(6):1019–1027, 2013. [doi:10.1016/j.ejc.2013.02.007]
[26] Gonzalo Fiz Pontiveros, Simon Griffiths, and Robert Morris: The triangle-free process and the Ramsey number R(3,k). Mem. AMS, 263(1274), 2020. [doi:10.1090/memo/1274]
[27] Alan Frieze and Tomasz Łuczak: On the independence and chromatic numbers of random regular graphs. J. Combin. Theory–B, 54(1):123–132, 1992. [doi:10.1016/0095-8956(92)90070-E]
[28] Magnús M. Halldórsson and Jaikumar Radhakrishnan: Improved approximations of independent sets in bounded-degree graphs via subgraph removal. Nord. J. Comput., 1(4):475–492, 1994. Preliminary version in SWAT’94.
[29] Fotis Iliopoulos: Stochastic Local Search and the Lovász Local Lemma. Ph. D. thesis, EECS Department, University of California, Berkeley, 2019. Available at UC Berkeley.
[30] Anders Johansson: Asymptotic choice number for triangle-free graphs. Technical Report 91-5, DIMACS, 1996.
[31] Ross J. Kang and Colin McDiarmid: Colouring random graphs. In Lowell W. Beineke and Robin J. Wilson, editors, Topics in chromatic graph theory, volume 156 of Encyclopedia Math. Appl., pp. 199–229. Cambridge Univ. Press, 2015. [doi:10.1017/CBO9781139519793.013]
[32] Richard M. Karp: Reducibility among combinatorial problems. In Raymond E. Miller, James W. Thatcher, and Jean D. Bohlinger, editors, Complexity of Computer Computations, pp. 85–103. Springer, 1972. [doi:10.1007/978-1-4684-2001-2_9]
[33] Richard M. Karp: The probabilistic analysis of some combinatorial search algorithms. In Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976), pp. 1–19, 1976. Available at UC Berkeley.
[34] Jeong Han Kim: On Brooks’ theorem for sparse graphs. Combin. Probab. Comput., 4(2):97–132, 1995. [doi:10.1017/S0963548300001528]
[35] Jeong Han Kim: The Ramsey number R(3,t) has order of magnitude t2∕log t. Random Struct. Algor., 7(3):173–207, 1995. [doi:10.1002/rsa.3240070302]
[36] Michael Molloy: The list chromatic number of graphs with small clique number. J. Combin. Theory–B, 134:264–284, 2019. [doi:10.1016/j.jctb.2018.06.007]
[37] Michael Molloy and Bruce Reed: Graph Colouring and the Probabilistic Method. Volume 23 of Algorithms and Combinatorics. Springer, 2002. [doi:10.1007/978-3-642-04016-0]
[38] Robin A. Moser: A constructive proof of the Lovász Local Lemma. In Proc. 41st STOC, pp. 343–350. ACM Press, 2009. [doi:10.1145/1536414.1536462]
[39] Robin A. Moser and Gábor Tardos: A constructive proof of the general Lovász Local Lemma. J. ACM, 57(2):11:1–15, 2010. [doi:10.1145/1667053.1667060]
[40] Alessandro Panconesi and Aravind Srinivasan: Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding bounds. SIAM J. Comput., 26(2):350–368, 1997. [doi:10.1137/S0097539793250767]
[41] Seth Pettie and Hsin-Hao Su: Distributed coloring algorithms for triangle-free graphs. Inform. Comput., 243:263–280, 2015. Preliminary version in ICALP’13. [doi:10.1016/J.IC.2014.12.018]
[42] Frank P. Ramsey: On a problem of formal logic. Proc. London Math. Soc., 30(4):264–286, 1929. [doi:10.1112/plms/s2-30.1.264]
[43] James B. Shearer: A note on the independence number of triangle-free graphs. Discr. Math., 46(1):83–87, 1983. [doi:10.1016/0012-365X(83)90273-X]
[44] James B. Shearer: On the independence number of sparse graphs. Random Struct. Algor., 7(3):269–271, 1995. [doi:10.1002/rsa.3240070305]
[45] Peter Ungar and Blanche Descartes: Solution for 4526: k-chromatic graphs without triangles. Amer. Math. Monthly, 61(5):352–353, 1954. [doi:10.2307/2307489]
[46] Vadim G. Vizing: Some unsolved problems in graph theory. Russ. Math. Surv., 23(6):125–141, 1968. [doi:10.1070/RM1968v023n06ABEH001252]
[47] Van H. Vu: A general upper bound on the list chromatic number of locally sparse graphs. Combin. Probab. Comput., 11(1):103–111, 2002. [doi:10.1017/S0963548301004898]
[48] Alexander A. Zykov: On some properties of linear complexes. Sbornik Math., 66(2):163–188, 1949. Available at Math-Net.Ru.
