Coloring a graph with Δ−1 colors: Conjectures equivalent to the Borodin–Kostochka conjecture that appear weaker

Benedict, 1978, vol. 642, 132 O.V. Borodin, Criterion of chromaticity of a degree prescription, in: Abstracts of IV All-Union Conf. on Th. Cybernetics, 1977, pp. 127–128. Borodin, 1977, On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density, J. Combin. Theory Ser. B, 23, 247, 10.1016/0095-8956(77)90037-5 Brooks, 1941, vol. 37, 194 Catlin, 1976 Catlin, 1979, Hajós graph-coloring conjecture: variations and counterexamples, J. Combin. Theory Ser. B, 26, 268, 10.1016/0095-8956(79)90062-5 D.W. Cranston, L. Rabern, Conjectures equivalent to the Borodin–Kostochka Conjecture that are a priori weaker, 2012. arXiv:1203.5380. D.W. Cranston, L. Rabern, Graphs with χ=Δ have big cliques, 2013. http://arxiv.org/abs/1305.3526. Emden-Weinert, 1998, Uniquely colourable graphs and the hardness of colouring graphs of large girth, Combin. Probab. Comput., 7, 375, 10.1017/S0963548398003678 Entringer, 1985, A short proof of Rubin’s block theorem, vol. 115, 367 P. Erdős, A.L. Rubin, H. Taylor, Choosability in graphs, in: Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium, vol. 26, 1979, pp. 125–157. Hladkỳ, 2010, Brooks’ theorem via the Alon–Tarsi theorem, Discrete Math., 310, 3426, 10.1016/j.disc.2010.07.019 Jensen, 1995 Kierstead, 2000, On the choosability of complete multipartite graphs with part size three, Discrete Math., 211, 255, 10.1016/S0012-365X(99)00157-0 King, 2011, Hitting all maximum cliques with a stable set using lopsided independent transversals, J. Graph Theory, 67, 300, 10.1002/jgt.20532 King, 2012, A fractional analogue of Brooks’ theorem, SIAM J. Discrete Math., 26, 452, 10.1137/110827879 Kostochka, 1980, Degree, density, and chromatic number, Metody Diskret. Anal., 35, 45 Kostochka, 1996, The colour theorems of Brooks and Gallai extended, Discrete Math., 162, 299, 10.1016/0012-365X(95)00294-7 Lovász, 1966, On decomposition of graphs, SIAM J. Algebr. Discrete Methods, 3, 237 Molloy, 2002 Mozhan, 1983, Chromatic number of graphs with a density that does not exceed two-thirds of the maximal degree, Metody Diskretn. Anal., 39, 52 Rabern, 2011, On hitting all maximum cliques with an independent set, J. Graph Theory, 66, 32, 10.1002/jgt.20487 Reed, 1999, A strengthening of Brooks’ theorem, J. Combin. Theory Ser. B, 76, 136, 10.1006/jctb.1998.1891 Reed, 2004, List colouring when the chromatic number is close to the order of the graph, Combinatorica, 25, 117, 10.1007/s00493-005-0010-x