, Since it is a much stronger form of Shearer's bound, one might wonder if it alone is enough to verify Conjecture 3.4.1. This does not seem to be the case. We remark however that Theorems 3.1.2 and 1.1.1 together immediately yield Conjectures 3.4.1 and 3.4.2 for regular triangle-free graphs, Here it seems natural to use Theorem 1.1.1 (Molloy-Johansson)

, Although we were preoccupied with triangle-free graphs, one could naturally investigate graphs not containing H as a subgraph for any fixed graph H. The following is in essence a more general form of

. .. -kempe-chain, 62 (a : b)-choosable, Index Symbols (a, b)

. .. L-colourable,

. .. L-colouring,

. .. Np,

P. .. ,

. .. , 51 s, t-flow

. .. Bipartite,

. .. Erd?s-rényi-model, , p.29

. .. Eulerian,

. .. Eulerian-path, , p.18

. .. Hall-ratio,

. .. Hamiltonian,

.. .. Hamiltonian-path, 14 hard-core distribution, vol.70

. .. Mst), Minimum Spanning Tree

.. .. Mycielski,

.. .. Mycielskian,

D. Achlioptas, F. Iliopoulos, and A. Sinclair, A New Perspective on Stochastic Local Search and the Lovasz Local Lemma, 2018.

M. Ajtai, J. Komlós, and E. Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A, vol.29, issue.3, pp.354-360, 1980.

M. Ajtai, J. Komlós, and E. Szemerédi, A dense infinite Sidon sequence, European J. Combin, vol.2, issue.1, pp.1-11, 1981.

N. Alon, Choice numbers of graphs: a probabilistic approach, Combin. Probab. Comput, vol.1, issue.2, pp.107-114, 1992.

N. Alon, Degrees and choice numbers, Random Structures Algorithms, vol.16, issue.4, pp.364-368, 2000.

N. Alon and M. Krivelevich, The choice number of random bipartite graphs, Annals of Combinatorics, vol.2, issue.4, pp.291-297, 1998.

N. Alon, M. Krivelevich, and B. Sudakov, Coloring graphs with sparse neighborhoods, J. Combin. Theory Ser. B, vol.77, issue.1, pp.73-82, 1999.

N. Alon and B. Mohar, The chromatic number of graph powers, Combin. Probab. Comput, vol.11, issue.1, pp.1-10, 2002.

N. Alon, Z. Tuza, and M. Voigt, Choosability and fractional chromatic numbers, Graphs and Combinatorics, vol.165, pp.31-38, 1995.

B. , Graphentheoretische extremalprobleme, Acta Mathematica Hungarica, vol.15, issue.3-4, pp.413-438, 1964.

B. Bajnok and G. Brinkmann, On the independence number of triangle free graphs with maximum degree three, J. Combin. Math. Combin. Comput, vol.26, pp.237-254, 1998.

L. W. Beineke, Derived graphs and digraphs. Beiträge zur Graphentheorie, pp.17-33, 1968.

A. Bernshteyn, The Johansson-Molloy theorem for DP-coloring, Random Structures & Algorithms, 2018.

N. Bhatnagar, A. Sly, and P. Tetali, Decay of correlations for the hardcore model on the d-regular random graph, Electron. J. Probab, vol.21, issue.9, p.42, 2016.

T. Bohman, The triangle-free process, Advances in Mathematics, vol.221, issue.5, pp.1653-1677, 2009.

T. Bohman and P. Keevash, Dynamic concentration of the triangle-free process, 2013.

B. Bollobás, Extremal Graph Theory, vol.11, 1978.

B. Bollobás, The independence ratio of regular graphs, Proc. Amer. Math. Soc, vol.83, issue.2, pp.433-436, 1981.

M. Bonamy, T. Kelly, P. Nelson, and L. Postle, Bounding ? by a fraction of ? for graphs without large cliques, 2018.

M. Bonamy, T. Perrett, and L. Postle, Colouring graphs with sparse neighbourhoods: Bounds and applications, 2018.

J. A. Bondy and M. Simonovits, Cycles of even length in graphs, J. Combinatorial Theory Ser. B, vol.16, pp.97-105, 1974.

O. V. Borodin and A. V. Kostochka, On an upper bound of a graph's chromatic number, depending on the graph's degree and density, J. Combinatorial Theory Ser. B, vol.23, issue.2-3, pp.247-250, 1977.

S. Brandt and S. Thomassé, Dense triangle-free graphs are four-colorable: A solution to the Erd?s-Simonovits problem, 2011.

R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc, vol.37, pp.194-197, 1941.

H. Bruhn and F. Joos, A stronger bound for the strong chromatic index, Combinatorics, Probability and Computing, vol.27, issue.1, pp.21-43, 2018.

W. Cames-van-batenburg, R. De-joannis-de-verclos, R. J. Kang, and F. Pirot, Bipartite induced density in triangle-free graphs, 2018.

Y. Caro, New results on the independence number, 1979.

A. Coja-oghlan and C. Efthymiou, On independent sets in random graphs, Random Structures & Algorithms, vol.47, issue.3, pp.436-486, 2015.

D. W. Cranston and L. Rabern, Brooks' theorem and beyond, Journal of Graph Theory, vol.80, issue.3, pp.199-225, 2015.

M. Cropper, A. Gyárfás, and J. Lehel, Hall ratio of the mycielski graphs, Discrete Mathematics, vol.306, issue.16, 1988.

E. Davies, R. De-joannis-de-verclos, R. J. Kang, and F. Pirot, Colouring triangle-free graphs with local list sizes, 2018.

E. Davies, R. De-joannis-de-verclos, R. J. Kang, and F. Pirot, Occupancy fraction, fractional colouring, and triangle fraction. arXiv e-prints, 2018.

E. Davies, M. Jenssen, W. Perkins, and B. Roberts, Independent sets, matchings, and occupancy fractions, J. Lond. Math. Soc, vol.96, issue.2, pp.47-66, 2017.

E. Davies, M. Jenssen, W. Perkins, and B. Roberts, On the average size of independent sets in triangle-free graphs, Proc. Amer. Math. Soc, vol.146, issue.1, pp.111-124, 2018.

M. Delcourt and L. Postle, On the list coloring version of reed's conjecture, The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17), vol.61, pp.343-349, 2017.

Z. Dvo?ák and L. Postle, Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, Journal of Combinatorial Theory, Series B, vol.129, pp.38-54, 2018.

Z. Dvo?ák, P. Ossona-de-mendez, and H. Wu, 1-subdivisions, fractional chromatic number and Hall ratio, 2018.

T. Emden-weinert, S. Hougardy, and B. Kreuter, Uniquely colourable graphs and the hardness of colouring graphs of large girth, Combin. Probab. Comput, vol.7, issue.4, pp.375-386, 1998.

P. Erd?os, Some remarks on the theory of graphs, Bull. Amer. Math. Soc, vol.53, issue.4, p.1947

P. Erd?os and G. Szekeres, A Combinatorial Problem in Geometry, Birkhäuser Boston, pp.49-56, 1987.

P. Erd?s, A. L. Rubin, and H. Taylor, Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, pp.125-157, 1979.

P. Erd?s, Graph theory and probability, Canad. J. Math, vol.11, pp.34-38, 1959.

P. Erd?s, Graph theory and probability, II. Canad. J. Math, vol.13, pp.346-352, 1961.

P. Erd?s, Problems and results in combinatorial analysis and graph theory, Proceedings of the First Japan Conference on Graph Theory and Applications, vol.72, pp.81-92, 1986.

P. Erd?s and A. , Chromatic number of finite and infinite graphs and hypergraphs, Special volume on ordered sets and their applications (L'Arbresle, vol.53, pp.281-285, 1982.

P. Erd?s, C. Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser, vol.12, issue.2, pp.313-320, 1961.

P. Erd?s and M. Simonovits, On a valence problem in extremal graph theory, Discrete Math, vol.5, pp.323-334, 1973.

P. Erd?s and A. Rényi, On the evolution of random graphs, Publication of the mathematical institute of the Hungarian academy of sciences, pp.17-61, 1960.

L. Esperet, R. Kang, and S. Thomassé, Separation choosability and dense bipartite induced subgraphs, Combinatorics, Probability and Computing, pp.1-13, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02275202

G. Exoo and R. Jajcay, Dynamic cage survey. The Electronic Journal of Combinatorics, 2008.

W. Feit and G. Higman, The nonexistence of certain generalized polygons, J. Algebra, vol.1, pp.114-131, 1964.

G. Fiz-pontiveros, S. Griffiths, and R. Morris, The triangle-free process and the Ramsey number R(3, k), Mem. Amer. Math. Soc, 2018.

K. Fraughnaugh and S. C. Locke, 11/30 (finding large independent sets in connected trianglefree 3-regular graphs), J. Combin. Theory Ser. B, vol.65, issue.1, pp.51-72, 1995.

A. Frieze and T. Luczak, On the independence and chromatic numbers of random regular graphs, Journal of Combinatorial Theory, Series B, vol.54, issue.1, pp.123-132, 1992.

F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B, vol.63, issue.1, pp.153-158, 1995.

J. Gimbel and C. Thomassen, Coloring triangle-free graphs with fixed size, Discrete Math, vol.219, issue.1-3, pp.275-277, 2000.

H. Grötzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe, vol.8, pp.109-120, 1958.

P. Hall, On representatives of subsets, J. London Math. Soc, vol.10, pp.26-30, 1935.

D. G. Harris, Some results on chromatic number as a function of triangle count, SIAM Journal on Discrete Mathematics, vol.33, issue.1, pp.546-563, 2019.

I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput, vol.10, issue.4, pp.718-720, 1981.

A. E. Ingham, On the difference between consecutive primes, Quart. J. Math, vol.8, issue.1, pp.255-266, 1937.

S. Janson, T. Luczak, and A. Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, 2000.

T. R. Jensen and B. Toft, Graph coloring problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, 1995.

G. P. Jin, Triangle-free four-chromatic graphs, Discrete Math, vol.145, issue.1-3, pp.151-170, 1995.

A. Johansson, Asymptotic choice number for triangle free graphs, 1996.

K. F. Jones, Independence in graphs with maximum degree four, J. Combin. Theory Ser. B, vol.37, issue.3, pp.254-269, 1984.

J. Kahn, Asymptotically good list-colorings, J. Combin. Theory Ser. A, vol.73, issue.1, pp.1-59, 1996.

J. Kahn, Asymptotics of the chromatic index for multigraphs, J. Combin. Theory Ser. B, vol.68, issue.2, pp.233-254, 1996.

T. Kaiser and R. J. Kang, The distance-t chromatic index of graphs, Combin. Probab. Comput, vol.23, issue.1, pp.90-101, 2014.

R. J. Kang and F. Pirot, Coloring Powers and Girth, SIAM J. Discrete Math, vol.30, issue.4, pp.1938-1949, 2016.

R. J. Kang and F. Pirot, Distance colouring without one cycle length, Combinatorics, Probability and Computing, vol.27, issue.5, pp.794-807, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01668633

M. Kano and A. Saito, factors of graphs. Discrete Mathematics, vol.47, pp.113-116, 1983.

F. Kardo?, D. Král, &. , and J. Volec, Fractional colorings of cubic graphs with large girth, SIAM J. Discrete Math, vol.25, issue.3, pp.1454-1476, 2011.

R. M. Karp, The probabilistic analysis of some combinatorial search algorithms, Algorithms and complexity: New directions and recent results, vol.1, p.19, 1976.

J. B. Kelly and L. M. Kelly, Paths and circuits in critical graphs, Amer. J. Math, vol.76, pp.786-792, 1954.

S. Khanna, N. Linial, and S. Safra, On the hardness of approximating the chromatic number, Combinatorica, vol.20, issue.3, pp.393-415, 2000.

K. Kilakos and B. A. Reed, Fractionally colouring total graphs, Combinatorica, vol.13, issue.4, pp.435-440, 1993.

J. H. Kim, On brooks' theorem for sparse graphs, Combinatorics, Probability and Computing, vol.4, issue.2, pp.97-132, 1995.

J. H. Kim, The Ramsey number R(3, t) has order of magnitude t 2 / log t, Random Structures Algorithms, vol.7, issue.3, pp.173-207, 1995.

A. D. King, Claw-free graphs and two conjectures on ?, ?, and ?, 2009.

D. König, Graphokés matrixok, Matematikaiés Fizikai Lapok, vol.38, pp.116-119, 1931.

J. Kratochvil, Z. Tuza, and M. Voigt, Brooks-type theorems for choosability with separation, Journal of Graph Theory, vol.27, issue.1, pp.43-49, 1998.

M. Kwan, S. Letzter, B. Sudakov, and T. Tran, Dense induced bipartite subgraphs in triangle-free graphs, 2018.

L. Lovász, On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hungar, vol.19, pp.59-67, 1968.

L. Lovász, On the ratio of optimal integral and fractional covers, Discrete Math, vol.13, issue.4, pp.383-390, 1975.

L. Lovász, Kneser's conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, vol.25, issue.3, pp.319-324, 1978.

M. Mahdian, The strong chromatic index of C 4 -free graphs, Random Structures Algorithms, vol.17, issue.3-4, pp.357-375, 2000.

W. Mantel, Problem 28, Wiskundige Opgaven, vol.10, p.320, 1907.

C. Mcdiarmid, Colouring random graphs, Annals of Operations Research, vol.1, issue.3, pp.183-200, 1984.
URL : https://hal.archives-ouvertes.fr/hal-01184397

M. Molloy, The list chromatic number of graphs with small clique number, J. Combin. Theory Ser. B, vol.134, pp.264-284, 2019.

M. Molloy and B. A. Reed, A bound on the strong chromatic index of a graph, J. Combin. Theory Ser. B, vol.69, issue.2, pp.103-109, 1997.

M. Molloy and B. A. Reed, A bound on the total chromatic number, Combinatorica, vol.18, issue.2, pp.241-280, 1998.

M. Molloy and B. A. Reed, Graph colouring and the probabilistic method, Algorithms and Combinatorics, vol.23, 2002.

J. W. Moon and L. Moser, On cliques in graphs, Israel Journal of Mathematics, vol.3, pp.23-28, 1965.

J. Mycielski, Sur le coloriage des graphs

, Colloq. Math, vol.3, pp.161-162, 1955.

J. , K-chromatic graphs without cycles of length ? 7, Comment. Math. Univ. Carolinae, vol.7, pp.373-376, 1966.

A. Nilli, Triangle-free graphs with large chromatic numbers, Discrete Math, vol.211, issue.1-3, pp.261-262, 2000.

S. E. Payne and J. A. Thas, Finite generalized quadrangles, Research Notes in Mathematics, vol.110, 1984.

J. Petersen, Die Theorie der regulären graphs, Acta Math, vol.15, issue.1, pp.193-220, 1891.

O. Pikhurko, A note on the Turán function of even cycles, Proc. Amer. Math. Soc, vol.140, issue.11, pp.3687-3692, 2012.

F. Pirot and J. Sereni, Fractional chromatic number, maximum degree and girth, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02096426

S. Poljak and Z. Tuza, Bipartite subgraphs of triangle-free graphs, SIAM J. Discrete Math, vol.7, issue.2, pp.307-313, 1994.

F. P. Ramsey, On a problem of formal logic, Proceedings of the London Mathematical Society, issue.1, pp.264-286, 1930.

B. A. Reed.-?, ?. , and ?. J. , Graph Theory, vol.27, pp.177-212, 1998.

N. Robertson, D. P. Sanders, P. D. Seymour, and R. Thomas, A new proof of the four-colour theorem, Electron. Res. Announc. Amer. Math. Soc, vol.2, issue.1, pp.17-25, 1996.

D. Saxton and A. Thomason, Hypergraph containers. Inventiones mathematicae, vol.201, pp.925-992, 2015.

C. E. Shannon, A theorem on coloring the lines of a network, J. Math. Physics, vol.28, pp.148-151, 1949.

J. B. Shearer, A note on the independence number of triangle-free graphs, Discrete Math, vol.46, issue.1, pp.83-87, 1983.

J. B. Shearer, On a problem of spencer, Combinatorica, vol.5, issue.3, pp.241-245, 1985.

J. B. Shearer, A note on the independence number of triangle-free graphs, ii, Journal of Combinatorial Theory, Series B, vol.53, issue.2, pp.300-307, 1991.

J. Spencer, Ramsey's theorem-a new lower bound, Journal of Combinatorial Theory, Series A, vol.18, issue.1, pp.108-115, 1975.

J. Spencer, Asymptotic lower bounds for Ramsey functions, Discrete Math, vol.20, issue.1, p.78, 1977.

W. Staton, Some Ramsey-type numbers and the independence ratio, Trans. Amer. Math. Soc, vol.256, pp.353-370, 1979.

C. Thomassen, Every planar graph is 5-choosable, J. Combin. Theory Ser. B, vol.62, issue.1, pp.180-181, 1994.

C. Thomassen, 3-list-coloring planar graphs of girth 5, J. Combin. Theory Ser. B, vol.64, issue.1, pp.101-107, 1995.

C. Thomassen, On the chromatic number of triangle-free graphs of large minimum degree, Combinatorica, vol.22, issue.4, pp.591-596, 2002.

V. G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz No, vol.3, pp.25-30, 1964.

M. Voigt, List colourings of planar graphs, Discrete Math, vol.120, issue.1-3, pp.215-219, 1993.

V. H. Vu, A general upper bound on the list chromatic number of locally sparse graphs, Combin. Probab. Comput, vol.11, issue.1, pp.103-111, 2002.

V. Wei, A lower bound on the stability number of a simple graph, 1981.

A. A. Zykov, On some properties of linear complexes, In Russian. English translation in Amer. Math. Soc. Transl, vol.24, issue.66, pp.163-188, 1949.