Abstract
It seems that combinatorics, and graph theory in particular, reached mathematical maturity relatively recently. Perhaps as a result of this there are not too many essential stories which have determined the course of the subject over a long period, enduring stories which appear again and again as a source of inspiration and motivate and challenge research.
Partially supported by the Project LL1201 ERCCZ CORES and by CE-ITI P202/12/G061 of GACR.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Ajtai, J. Komlós, E. Szemerédi, A note on Ramsey numbers, J. Combi. Th. Series A, 29 (1980), 354–360.
M. Ajtai, J. Komlós, E. Szemerédi, An O(n log n) sorting network, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983, 1–9.
N. Alon, Discrete Mathematics: methods and challenges, Proc. of the International Congress of Mathematicians (ICM), Beijing 2002, China, Higher Education Press (2003), 119–135.
N. Alon, V. Rödl, Sharp bounds for some multicolor Ramsey numbers, Combinatorica 25 (2005), 125–141.
N. Alon, J. H. Spencer, The probabilistic method Second ed. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, 2000.
O. Angel, A. Kechris, R. Lyons, Random Orderings and Unique Ergodicity of Automorphism Groups, arXiv: 1208.2389 (2012).
L. Barto, M. Kozik, New conditions for Taylor varieties and CSP, In: Proceedings of LICS’10, IEEE, 2010, 100–109.
S. Baum, M. Stiebitz, Coloring Of Graphs Without Short Odd Paths Between Vertices Of The Same Color Class, (preprint, TU Ilmenau).
D. Bokal, G. Fijavž, M. Juvan, P. M. Kayll, B. Mohar, The circular chromatic number of a digraph, J. Graph Theory 46 (2004), no. 3, 227–240.
B. Bollobás, Random Graphs, Academic Press, 1985.
B. Bollobás, Modern Graph Theory, Springer-Verlag, 1998.
B. Bollobás and N. Sauer, Uniquely colorable graphs with large girth, Can. J. Math. 28(1976), 1340–1344.
J. A. Bondy, U. S. R. Murty, Graph theory, Graduate Texts in Mathematics, 244, Springer, 2008.
G. Brightwell, On the complexity of diagram testing, Order 10,4 (1983), 297–303.
A. A. Bulatov, P. Jeavons, A. A. Krokhin, Classifying the Complexity of Constraints Using Finite Algebras, SIAM J. Comput. 34(3), 2005, 720–742.
G. Cherlin, S. Shelah, N. Shi, Universal graphs with forbidden subgraphs and algebraic closure, Adv. in Applied Math. 22 (1999), 454–491.
G. Cherlin, N. Shi, Graphs omitting a finite set of cycles, J. of Graph Th. 21 (1997), 351–355.
B. Codenotti, P. Pudlák, J. Resta, Some structural properties of low rank matrices related to computational complexity, Theoretical Computer Sci. 235 (2000), 89–107.
B. Descartes, A three colour problem, Eureka 21, 1947.
R. Diestel, Graph theory, Graduate Texts in Mathematics, 173, Springer, Heidelberg, 2010.
T. Emden-Weinert, S. Hongardy, B. Kreutzer, Uniquelly colorable graphs and hardness of colouring of graphs of large girth, Comb. Prob. Comp. 7,4 (1998), 375–386.
P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34–38.
P. Erdős, Problems and results in combinatorial analysis and graph theory, In: Proof Techniques in Graph Theory, Academic Press, 1969, 27–35.
P. Erdős, A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99.
P. Erdős, J. Nešetřil, V. Rödl On Pisier type problems and results (combinatorial applications to number theory), In: Mathematics of Ramsey Theory, Springer 1990, 214–231.
P. Erdős, C. A. Rogers, The construction of certain graphs, Canad. J. Math. 14 (1962), 702–707.
P. Erdős, E. Specker, On a theorem in the theory of relations and a solution of a problem of Knaster, Colloq. Math. 8 (1961), 19–21.
T. Feder, M. Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory, SIAM J. Comput. 28, 1 (1999), 57–104.
R. Graham and B. Rothschild and J. Spencer, Ramsey Theory, Wiley, New York, 1990.
D. Greenwell and L. Lovász, Applications of product coloring, Acta Math. Acad. Sci. Hungar. 25(1974), 335–340.
A. Gyárfás, T. Jensen, M. Stiebitz, On graphs with strongly independent colour-classes, JGT 46 (2004), 1–14.
A. Hajnal, J. Pach, Monochromatic paths in infinite graphs, In: Finite and Infinite Sets, Coll. Math. Soc. J. Bolyai, Eger, 1981, 359–369.
A. Harutyunyan, P. M. Kayll, B. Mohar, L. Rafferty, Uniquely D-colourable Digraphs with Large Girth, Canad. J. Math. Vol. 64 (6), 2012, 1310–1328.
H. Hatami, Random cubic graphs are not homomorphic to the cycle of size 7, J. Comb. Th. B 93 (2005), 319–325.
P. Hell, J. Nešetřil, Graphs and homomorphisms, Oxford University Press, 2004.
P. Hell, J. Nešetřil, Colouring, Constraint Satisfaction, and Complexity, Comp. Sci. Review 2,3 (2008) 134–164.
S. Hoory, N. Linial, A. Widgerson, Expander graphs and their applications, Bulletin (New series) of the American Mathematical Society 43 (4), 2006, 439–561.
S. Janson, T. Luczak, A. Ruczinski, Random Graphs, Wiley, 2000.
P. Jeavons, On the algebraic structure of combinatorial problems, Theor. Comp. Sci 200 (1998), 185–204.
J. Kahn, Recent results on some not-so-recent hypergraph matching and covering problems, Proc. 1st Int’l Conference on Extremal Problems for Finite Sets, Visegrad, 1991.
A. Kechris, Pestov, S. Todorcevic, Fraïssé limits, Ramsey theory and topological dynamics of automorphism groups, Geometrical and Functional Analysis 15(1), 2005, 106–189.
J. Kelly and L. Kelly, Path and circuits in critical graphs, Amer. J. Math. 76:786–792, 1954.
J. H. Kim, The Ramsey Number R(3,t) has order of magnitude t 2/log t, Random Structures and Algorithms 7 (1995), 173–207.
A. V. Kostochka J. Nešetřil, Properties of Descartes’ construction of triangle-free graphs with high chromatic number, Combin. Probab. Comput. 8(1999), no. 5, 467–472.
A. Kostochka, J. Nešetřil, P. Smolíková, Coloring and homomorphism of degenerate and bounded degree graphs, Discrete Math. 233, 1–3 (2001), 257–276.
A. V. Kostochka, V. Rödl, Constructions of Sparse Uniform Hypergraphs with High Chromatic Number, Random tructures and Algorithms, 2009, 46–56.
I. Kříž, A hypergraph free construction of highly chromatic graphs without short cycles, Combinatorica 9 (1989), 227–229.
I. Kříž, J. Nešetřil, Chromatic number of the Hasse diagrams, eyebrows and dimension, Order 8 /1991/, 41–48.
G. Kun, Constraints, MMSNP and expander relational structures, arXiv: 0706.1701 (2007).
G. Kun, M. Szegedy, A new line of attack on the dichotomy conjecture, STOC 2009, 725–734. See also Electronic Coll. on Comp. Compl. (ECCC) 16:59 (2009), 44p.
B. Larose, C. Tardif, Graph coloring problems, Wiley, 1995.
J. Lenz, D. Mubayi, The poset of hypergraph quasirandomness, The Poset of Hypergraph Quasirandomness, arXiv:1208.5978 au][math.CO] 29 Aug 2012.
L. Lovász, On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hungar. 19 (1968), 59–67.
L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory. Ser. A 25 (1978), 319–324.
L. Lovász, Combinatorial Problems and Exercises, Akad. Kiad, Budapest, 1979.
A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs, Combinatorica, 8(3), 1988, 261–277.
M. Mares, The saga of minimum spanning trees, Comp. Sci. Review 2 (2008), 165–221.
G. A. Margulis, Explicit constructions of graphs without short cycles and low density codes, Problemy Pereači Informacii, 9(4), 1973, 71–80.
J. Matoušek, Using the Borsuk-Ulam theorem, Lectures on topological methods in combinatorics and geometry, Springer, 2003.
M. Molloy, B. Reed, Graph colouring and the probabilistic method, Algorithms and Combinatorics, 23, Springer, 2002.
V. Müller, On colorable critical and uniquely colorable critical graphs, in: Recent Advances in Graph Theory (ed. M. Hiedler), Academia, Prague, 1975.
V. Müller, On coloring of graphs without short cycles, Discrete Math., 26(1979), 165–179.
J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3, 161–162, 1955.
J. Nešetřil, K-chromatic graphs without cycles of length ≤ 7, (in Russian), Comment. Math. Univ. Carol., 7, 3 (1966), 373–376.
J. Nešetřil, On uniquely colorable graphs without short cycles, Časopis Pěst. Mat. 98 (1973), 122–125.
J. Nešetřil, For graphs there are only four types of hereditary Ramsey classes, J. Combin. Theory Ser. B 46, (1989), no. 2, 127–132.
J. Nešetřil, Ramsey Theory, In: Handbook of Combinatorics (ed. R. L. Graham, M. Grötschel, L. Lovász), North-Holland, 1995, 1331–1403.
J. Nešetřil, P. Osssona de Mendez, Sparsity — Graph, Structures, and Algorithms, Springer, 2012.
J. Nešetřil, V. Rödl, On a probabilistic graph-theoretic Method, Proc. Amer. Math. Soc. 72 (1978), 417–421.
J. Nešetřil, V. Rödl, A short proof of the existence of restricted Ramsey graphs by means of a partite construction, Combinatorica 1, 2 (1982), 199–202.
J. Nešetřil, V. Rödl, Sparse Ramsey graphs, Combinatorica 4, 1 (1984), 71–78.
J. Nešetřil, V. Rödl, Combinatorial partitions of finite posets and lattices — Ramsey lattices, Algebra Univ. 19 (1984), 106–119
J. Nešetřil, V. Rödl, Complexity of diagrams, Order 3 (1987), 321–330.
J. Nešetřil, V. Rödl, Chromatically optimalrigid graphs, J. Combin. Th.(B), 46(1989), 133–141.
J. Nešetřil, V. Rödl, More on complexity of diagrams, Comm. Math. Univ. Carol. 36,2 (1995), 269–278.
J. Nešetřil, V. Rödl, Partitions of Finite Relational and Set Systems, J. Comb. Th. A 22,3 (1977), 289–312.
J. Nešetřil, V. Rödl, Partition (Ramsey) Theory — a survey, In: Coll. Math. Soc. János Bolyai, 18. Combinatorics, Keszthely 1976, North Holland, 1978, 759–792.
J. Nešetřil, M. Siggers, L. Zadori, A Combinatorial Constraint Satisfaction Problem Dichotomy Classication Conjecture, European J. Comb. 31 (1), 2010, 280–296.
J. Nešetřil, X. Zhu, On sparse graphs with given colorings and homomorphisms, J. Combin. Theory Ser. B 90(2004), no. 1, 161–172.
V. Rödl, On the chromatic number of subgraphs of a given graph, Proc. Amer. Math. Soc. 64 (1977), 370–371.
V. Rödl, On a packing and covering problem, Europ. J. Combinatorics 5 (1985), 69–78.
V. Rödl, L. Thoma, The complexity of cover graph recognition for some vertices of finite lattices, Order 12,4 (1995), 351–374.
G. Simonyi and G. Tardos, Local chromatic number, Ky Fan’s theorem, and circular colorings, Combinatorica 26 (2006), 587–620.
J. Spencer, Ten Lectures on the Probabilistic Method, Society for Industrial and Applied Mathematics, 1987.
I. M. Wanless, N. C. Wormald, Regular graphs with no homomorphisms onto cycles, J. Comb. Th. B 82 (2001), 155–160.
X. Zhu, Uniquely H-colorable graphs with large girth, J. Graph Theory, 23 (1996), 33–41.
A. A. Zykov, On some properties of linear complexes, Mat. Sbornik 24:313–319, 1949. (In Russian).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Additional information
Remembering dědeček Paul Erdős
Rights and permissions
Copyright information
© 2013 János Bolyai Mathematical Society and Springer-Verlag
About this chapter
Cite this chapter
Nešetřil, J. (2013). A Combinatorial Classic — Sparse Graphs with High Chromatic Number. In: Lovász, L., Ruzsa, I.Z., Sós, V.T. (eds) Erdős Centennial. Bolyai Society Mathematical Studies, vol 25. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39286-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-39286-3_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39285-6
Online ISBN: 978-3-642-39286-3
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)