Kolorowanie grafów bez dużych klik

• Autorzy: Walczak B.
• Języki publikacji: PL

Abstrakty

PL

Niniejsze opracowanie poświęcone jest jednemu z wielu aspektów kolorowania grafów – zależności liczby chromatycznej od rozmiaru najliczniejszej kliki.

Słowa kluczowe

PL

grafy; grafy doskonałe; grafy przedziałowe; liczba chromatyczna grafu; hipoteza Gyárfása-Sumnera; geometryczne grafy przecięć

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Wiadomości Matematyczne
• Rocznik: 2018
• Tom: T. 54, Nr 2
• Strony: 177--189
• Opis fizyczny: Bibliogr. 27 poz., rys.

Twórcy

autor

Walczak B.

• Zespół Katedr i Zakładów Informatyki Matematycznej, Wydział Matematyki i Informatyki, Uniwersytet Jagielloński, Kraków, Polska

Bibliografia

• [1] K. Appel, W. Haken, Every planar map is four colorable, Bull. Am. Math. Soc. 82 (1976), nr 5, 711-712.
• [2] K. Appel, W. Haken, Every Planar Map Is Four-Colorable, Contemp. Math., t. 98, AMS, Providence 1989.
• [3] E. Asplund, B. Grünbaum, On a coloring problem, Math. Scand. 8 (1960), 181-188.
• [4] C. Berge, Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Nat. Reihe 10 (1961), 114-115.
• [5] J. P. Burling, On Coloring Problems of Families of Polytopes, PhD thesis, University of Colorado, Boulder 1965.
• [6] M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Ann. Math. 164 (2006), nr 1, 51-229.
• [7] M. Chudnovsky, A. Scott, P. Seymour, Induced subgraphs of graphs with large chromatic number. III. Long holes, Combinatorica 37 (2017), nr 6, 1057-1072.
• [8] M. Chudnovsky, A. Scott, P. Seymour, Induced subgraphs of graphs with large chromatic number. XII. Distant stars, dostępne pod adresem arXiv:1711.08612.
• [9] M. Chudnovsky, A. Scott, P. Seymour, S. Spirkl, Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes, dostępne pod adresem arXiv: 1701.07217.
• [10] P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34-38.
• [11] P. Erdős, A. Hajnal, Some remarks on set theory. IX. Combinatorial problems in measure theory and set theory, Michigan Math. J. 11 (1964), nr 2, 107-127.
• [12] L. Esperet, Graph Colorings, Flows and Perfect Matchings, habilitation thesis, Université Grenoble Alpes 2017.
• [13] D. R. Fulkerson, O. Gross, Incidence matrices and interval graphs, Pacific J. Math. 15 (1965), nr 3, 835-855.
• [14] H. Grötzsch, Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-U. Halle-Wittenberg Math.-Nat. Reihe 8 (1959), 109-120.
• [15] A. Gyárfás, On Ramsey covering-numbers, [w:] Infinite and Finite Sets, t. 2, Colloq. Math. Soc. János Bolyai, t. 10, North-Holland, Amsterdam 1975, 801-816.
• [16] A. Gyárfás, On the chromatic number of multiple interval graphs and overlap graphs, Discrete Math. 55 (1985), nr 2, 161-166 (Corrigendum, Discrete Math. 62 (1986), nr 3, 333).
• [17] A. Gyárfás, Problems from the world surrounding perfect graphs, Zastos. Mat. 19 (1987), nr 3-4, 413-441.
• [18] H. A. Kierstead, S. G. Penrice, Radius two trees specify χ-bounded classes, J. Graph Theory 18 (1994), nr 2, 119-129.
• [19] J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955), nr 2, 161-162.
• [20] A. Pawlik, J. Kozik, T. Krawczyk, M. Lasoń, P. Micek, W. T. Trotter, B. Walczak, Triangle-free intersection graphs of line segments with large chromatic number, J. Comb. Theory Ser. B 105 (2014), 6-10.
• [21] A. Scott, Induced trees in graphs of large chromatic number, J. Graph Theory 24 (1997), nr 4, 297-311.
• [22] A. Scott, P. Seymour, Induced subgraphs of graphs with large chromatic number. I. Odd holes, J. Comb. Theory Ser. B 121 (2016), 68-84.
• [23] A. Scott, P. Seymour, Induced subgraphs of graphs with large chromatic number. XIII. New brooms, dostępne pod adresem arXiv:1807.03768.
• [24] A. Scott, P. Seymour, A survey of χ-boundedness, dostępne pod adresem arXiv: 1812.07500.
• [25] A. Soifer, The Mathematical Coloring Book, Springer, New York 2009.
• [26] A. Suk, Coloring intersection graphs of x-monotone curves in the plane, Combinatorica 34 (2014), nr 4, 487-505.
• [27] D. P. Sumner, Subtrees of a graph and the chromatic number, [w:] The Theory and Applications of Graphs, Wiley, New York 1981, 557-576.