Skip to main content
Log in

On the minimal number of edges in color-critical graphs

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

A graphG isk-critical if it has chromatic numberk, but every proper subgraph of it is (k−1)-colorable. This paper is devoted to investigating the following question: for givenk andn, what is the minimal number of edges in ak-critical graph onn vertices, with possibly some additional restrictions imposed? Our main result is that for everyk≥4 andn>k this number is at least\(\left( {\frac{{k - 1}}{2} + \frac{{k - 3}}{{2(k^2 - 2k - 1)}}} \right)n\), thus improving a result of Gallai from 1963. We discuss also the upper bounds on the minimal number of edges ink-critical graphs and provide some constructions of sparsek-critical graphs. A few applications of the results to Ramsey-type problems and problems about random graphs are described.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. N. Alon andJ. H. Spencer:The probabilistic method, Wiley, New York, 1992.

    Google Scholar 

  2. B. Bollobás:Random graphs, Academic Press, New York, 1985.

    Google Scholar 

  3. B. Bollobás andH. R. Hind: Graphs without large triangle-free subgraphs,Discrete Math. 87 (1991), 119–131.

    Google Scholar 

  4. R. L. Brooks: On colouring the nodes of a network,Proc. Cambridge Phil. Soc.,37 (1941), 194–197.

    Google Scholar 

  5. G. A. Dirac: A theorem of R. L. Brooks and a conjecture of H. Hadwiger, Proc. London Math. Soc.7 (1957), 161–195.

    Google Scholar 

  6. P. Erdős: Some new applications of probability methods to combinatorial analysis and graph theory,Proc. 5th S.E. Conf. in Combinatorics, Graph Theory and Computing, (1974), 39–51.

  7. P. Erdős andC. A. Rogers: The construction of certain graphs,Canad. J. Math.,14 (1962), 702–707.

    Google Scholar 

  8. P. Erdős andP. Tetali: Representations of integers as the sum ofk terms,Random Struct. Alg.,1 (1990), 245–261.

    Google Scholar 

  9. M. Fekete: Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koefficienten,Math. Z.,17 (1923), 228–249.

    Google Scholar 

  10. T. Gallai: Kritische Graphen I,Publ. Math. Inst. Hungar. Acad. Sci.,8 (1963), 165–192.

    Google Scholar 

  11. T. R. Jensen andB. Toft:Graph coloring problems, Wiley, New York, 1995.

    Google Scholar 

  12. H. A. Kierstead, E. Szemerédi andW. T. Trotter: On coloring graphs with locally small chromatic number,Combinatorica,4 (1984), 183–185.

    Google Scholar 

  13. M. Krivelevich:K S-free graphs without largeK r-free subgraphs,Combinat., Probab. Comput.,3 (1994), 349–354.

    Google Scholar 

  14. M. Krivelevich: Bounding Ramsey numbers through large deviation inequalities,Random Struct. Alg.,7 (1995), 145–155.

    Google Scholar 

  15. N. Linial andYu. Rabinovich: Local and global clique numbers,J. Combin. Theory, Ser. B.,61 (1994), 5–15.

    Google Scholar 

  16. T. Luczak: A note on the sharp concentration of the chromatic number of random graphs,Combinatorica,11 (1991), 295–297.

    Google Scholar 

  17. V. D. Milman andG. Schechtman:Asymptotic theory of finite dimensional normed spaces, Lecture Notes in Mathematics 1200, Springer Verlag, Berlin and New York, 1986.

    Google Scholar 

  18. H. Sachs andM. Stiebitz: Colour-critical graphs with vertices of low valency,Annals of Discrete Math.,41 (1989), 371–396.

    Google Scholar 

  19. H. Sachs andM. Stiebitz: On constructive, methods in the theory of colour-critical graphs,Discrete Math.,74 (1989), 201–226.

    Google Scholar 

  20. E. Shamir andJ. Spencer: Sharp concentration of the chromatic number of random graphsG n,p ,Combinatorica,7 (1987), 124–129.

    Google Scholar 

  21. M. Stiebitz: Proof of a conjecture of T. Gallai concernign connectivity properties of colour-critical graphs,Combinatorica,2 (1982), 315–323.

    Google Scholar 

  22. B. Toft: Color-critical graphs, and hypergraphs,J. Combin. Theory, Ser. B,16 (1974), 145–161.

    Google Scholar 

  23. D. A. Youngs: 4-Chromatic projective graphs,J Graph Theory,21 (1996), 219–227.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Additional information

This research forms part of a Ph.D. thesis written by the author under the supervision of Professor Noga Alon. Research supported in part by a Charles Clore Fellowship.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Krivelevich, M. On the minimal number of edges in color-critical graphs. Combinatorica 17, 401–426 (1997). https://doi.org/10.1007/BF01215921

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01215921

Mathematics Subject Classification (1991)

Navigation