Families of planar 4-homogeneous 4-critical graphs

L. S. Mel'nikov

Diskretnyj analiz i issledovanie operacij, Tome 11 (2004) no. 1, pp. 79-115.

Bibliographie

[1] Aksenov V. A., “O prodolzhenii 3-raskraski na ploskikh grafakh”, Diskretnyi analiz, Sb. nauch. tr., no. 26, In-t matematiki SO AN SSSR, Novosibirsk, 1974, 3–19 | MR

[2] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[3] Dobrynin A. A., Melnikov L. S., Pyatkin A. V., “4-khromaticheskie reberno-kriticheskie regulyarnye grafy s vysokoi svyaznostyu”, Rossiiskaya konferentsiya “Diskretnyi analiz i issledovanie operatsii”, Materialy konferentsii, Izd-vo In-ta matematiki, Novosibirsk, 2002, 25–30

[4] Dobrynin A. A., Melnikov L. S., Pyatkin A. V., “Kriticheskie grafy Erdesha i Diraka chetnoi stepeni”, Diskret. analiz i issled. operatsii. Ser. 1, 10:3 (2003), 12–22 | MR | Zbl

[5] Doiber V. A., Kostochka A. V., Zaks Kh., “Bolee korotkoe dokazatelstvo teoremy Diraka o chisle reber v khromaticheski kriticheskikh grafakh”, Diskret. analiz i issled. operatsii. Ser. 1, 3:4 (1996), 28–34 | MR

[6] Evstigneev V. A., Kasyanov V. N., Tolkovyi slovar po teorii grafov v informatike i programmirovanii, Nauka, Novosibirsk, 1999 | Zbl

[7] Evstigneev V. A., Melnikov L. S., Zadachi i uprazhneniya po teorii grafov i kombinatorike, NGU, Novosibirsk, 1981 | MR

[8] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Nauka, M., 1990 | MR | Zbl

[9] Abbott H. L., Zhou B., “On a conjecture of Gallai concerning complete subgraphs of $k$-critical graphs”, Discrete Math., 100:1–3 (1992), 223–228 | DOI | MR | Zbl

[10] Aksionov V. A., Mel'nikov L. S., “Essay on the theme: the three-color problem”, Combinatorics, Colloquia Math. Soc. János Bolyai, 18, North-Holland, Amsderdam, 1978, 23–34 | MR

[11] Brinkmann G., Meringer M., “The smallest 4-regular 4-chromatic graphs with girth 5”, Graph Theory Notes N.Y., 32 (1997), 40–41 | MR

[12] Brooks R. L., “On coloring the nodes of a network”, Proc. Cambridge Phil. Soc., 37, 1941, 194–197 | MR | Zbl

[13] Brown W. G.,Moon J. W., “Sur les ensembles de sommets indépendents dans les graphes chromatiques minimaux”, Canad. J. Math., 21:2 (1969), 274–278 | MR | Zbl

[14] de Bruijn N. G., Erdős P., “A colour problem for infinite graphs and a problem in the theory of relations”, Nederl. Acad. Wetensch. Proc. Ser. A., Indag. Math., 54, 1951, 369–373 | MR

[15] Chao C.-Y., “A critically chromatic graph”, Discrete Math., 172:1–3 (1997), 3–7 | DOI | MR | Zbl

[16] Dirac G. A., “Note on the colouring of graphs”, Mathematische Zeitschrift, 54:4 (1951), 347–353 | DOI | MR | Zbl

[17] Dirac G. A., “A property of 4-chromatic graphs and some remarks on critical graphs”, J. London Math. Soc., 27 (1952), 85–92 | DOI | MR | Zbl

[18] Dirac G. A., “Some theorems on abstract graphs”, Proc. London Math. Soc. (Third Ser.), 2, 1952, 69–81 | MR | Zbl

[19] Dirac G. A., “Map colour theorems”, Canad. J. Math., 4:2 (1952), 480–490 | MR | Zbl

[20] Dirac G. A., “The structure of $k$-chromatic graphs”, Fund. Math., 40 (1953), 42–55 | MR | Zbl

[21] Dirac G. A., “The coloring of maps”, J. London Math. Soc., 28 (1953), 476–480 | DOI | MR | Zbl

[22] Dirac G. A., “A theorem of R. L. Brooks and a conjecture of H. Hadwiger”, Proc. London Math. Soc. (3), 7:26 (1957), 161–195 | DOI | MR | Zbl

[23] Dirac G. A., “Short proof of a map colour theorem”, Canad. J. Math., 9:2 (1957), 225–226 | MR | Zbl

[24] Dirac G. A., “4-chrome Graphen und vollständige 4-Graphen”, Math. Nachr., 22:1–2 (1960), 51–60 | DOI | MR | Zbl

[25] Dirac G. A., “In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen”, Math. Nachr., 22:1–2 (1960), 61–85 | DOI | MR | Zbl

[26] Dirac G. A., “On the structure of 5- and 6-chromatic abstract graphs”, J. Reine Angewandte Math., 214–215 (1964), 45–52 | MR

[27] Dirac G. A., “The number of edges in critical graphs”, J. Reine Angewandte Math., 268–269 (1974), 150–164 | MR | Zbl

[28] Dobrynin A. A., Melnikov L. S., Pyatkin A. V., “On 4-chromatic edge-critical regular graphs of high connectivity”, Discrete Math., 260:1–3 (2003), 315–319 | DOI | MR | Zbl

[29] Dobrynin A. A., Melnikov L. S., Pyatkin A. V., “Regular 4-critical graphs of even degree”, J. Graph Theory, 46:2 (2004), 103–130 | DOI | MR | Zbl

[30] Dobrynin A. A., Melnikov L. S., Pyatkin A. V., “Computer search for regular 4-critical graphs”, Discrete. Math., submitted

[31] Erdős P., “On some aspects of my work with Gabriel Dirac Graph theory in memory of G. A. Dirac”, Annals of Discrete Mathematics, 41, North-Holland, Amsterdam, 1989, 111–116 | MR

[32] Fisk S., “The non-existance of colorings”, J. Combin. Theory. Ser. B., 24:2 (1978), 247–248 | DOI | MR | Zbl

[33] Gallai T., “Kritische Graphen I”, Publ. Math. Inst. Hungar. Acad. Sci., 8:1–2 (1963), 165–192 | MR | Zbl

[34] Gallai T., “Kritische Graphen II”, Publ. Math. Inst. Hungar. Acad. Sci., 8:3–4 (1963), 373–395 | MR | Zbl

[35] Gallai T., “Critical graphs”, Theory of graphs and its applications (Proc. Symp. Smolenice, 1963), Publ. House Czechoslovak Acad. Sci., Prague, 1964, 43–45 | MR

[36] Garey M. R., Johnson D. S., Srockmeyer L. J., “Some simplified NP-complete graph problems”, Theoret. Comput. Sci., 1:3 (1976), 237–267 | DOI | MR | Zbl

[37] Grötzsch H., “Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel”, Univ. Halle-Wittenberg Math.-Natur. Reihe, 8:1 (1959), 109–119 | MR

[38] Grünbaum B., “Grötzsch's theorem on 3-colorings”, Michigan Math. J., 10:3 (1963), 303–310 | DOI | MR | Zbl

[39] Grünbaum B., “A problem in graph coloring”, Amer. Math. Monthly, 77:10 (1970), 1088–1092 | DOI | MR

[40] Grünbaum B., “The edge-density of 4-critical planar graphs”, Combinatorica, 8:1 (1988), 137–139 | DOI | MR | Zbl

[41] Hajós G., “Über eine Konstruktion nicht $n$-färbbarer Graphen”, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 10:1–2 (1961), 116–117

[42] Heuberger C., “On planarity and colorability of circulant graphs”, Discrete Math., 268:1–3 (2003), 153–169 | DOI | MR | Zbl

[43] Jensen T. R., “Dense critical and vertex-critical graphs”, Discrete Math., 258:1–3 (2002), 63–84 | DOI | MR | Zbl

[44] Jensen T. R., Royle G. F., “Small graphs of chromatic number 5: a computer search”, J. Graph Theory, 19:1 (1995), 107–116 | DOI | MR | Zbl

[45] Jensen T., Toft B., Graph coloring problems, John Wiley Sons, New York, 1995 | MR | Zbl

[46] Jensen T., Toft B., “25 Pretty graph coloring problems”, Discrete Math., 229:1–3 (2001), 167–169 | DOI | MR | Zbl

[47] Karp R., “Reducibility among combinatorial problems”, Complexity of Computer Computation, 1972, 85–103, Plenum Press, New York, London ; Karp R. M., “Svodimost kombinatornykh problem”, Kiberneticheskii sbornik (novaya seriya), no. 12, Mir, M., 1975, 16–38 | MR | MR

[48] Koester G., “Bemerkung zu einem Problem von H. Grötzsch”, Wiss. Z. Univ. Halle, 33 (1984), 129 | Zbl

[49] Koester G., “Coloring problems on a class of 4-regular planar graphs”, Graphs, hypergraphs and applications, Teubner–Texte Math., 73, Teubner, Leipzig, 1985, 102–105 | MR | Zbl

[50] Koester G., “Note to a problem of T. Gallai and G. A. Dirac”, Combinatorica, 5:3 (1985), 227–228 | DOI | MR | Zbl

[51] Koester G., “4-critical 4-valent planar graphs constructed with crowns”, Math. Scand., 67 (1990), 15–22 | MR | Zbl

[52] Koester G., “On 4-critical planar graphs with high edge density”, Discrete Math., 98:2 (1991), 147–151 | DOI | MR | Zbl

[53] Kostochka A. V., Stiebitz M., “Colour-critical graphs with few edges”, Discrete Math., 191:1–3 (1998), 125–137 | DOI | MR | Zbl

[54] Kostochka A. V., Stiebitz M., “Excess in colour-critical graphs”, Graph theory and combinatorial biology (Balatonlelle, 1996), Bolyai Soc. Math. Stud., 7, Janos Bolyai Math. Soc., Budapest, 1999, 87–99 | MR | Zbl

[55] Kostochka A. V., Stiebitz M., “On the number of edges in colour-critical graphs and hypergraphs”, Combinatorica, 20:4 (2000), 521–530 | DOI | MR | Zbl

[56] Kostochka A. V., Stiebitz M., “A new lower bound on the number of edges in colour-critical graphs and hypergraphs”, J. Combin. Theory. Ser. B., 87:2 (2003), 374–402 | DOI | MR | Zbl

[57] Krivelevich M., “On the minimal number of edges in color-critical graphs”, Combinatorica, 17:3 (1997), 401–426 | DOI | MR | Zbl

[58] Krivelevich M., “An improved bound on the minimal number of edges in color-critical graphs”, Electron J. Combin., 5:1 (1998), 4 | MR | Zbl

[59] Kronk H. V., Mitchem J., “On Dirac's generalization of Brooks' theorem”, Canad. J. Math., 24:5 (1972), 805–807 | MR | Zbl

[60] Lovász L., “Independent set in critical chromatic graphs”, Studia Sci. Math. Hungar., 8:1–2 (1973), 165–168 | MR

[61] Melnikov L. S., “On problems of Gallai–Dirac and Grunbaum”, Discrete Math., submitted

[62] Melnikov L. S., Vizing V. G., “New proof of Brook's theorem”, J. Combin. Theory, 7:4 (1969), 289–290 | DOI | MR | Zbl

[63] Pyatkin A. V., “6-regular 4-critical graph”, J. Graph Theory, 41:4 (2002), 286–291 | DOI | MR | Zbl

[64] Sachs H., Stiebitz M., “Colour-critical graphs with vertices of low valency”, Amsterdam, Annals of Discrete Math., 41, North-Holland, 1989, 371–396 | MR

[65] Simonovits M., “On colour-critical graphs”, Studia Sci. Math. Hungar., 7:1–2 (1972), 67–81 | MR | Zbl

[66] Stiebitz M., Beiträge zur Theorie der färbungskritischen Graphen, Dissertation zu Erlangung des akademishen Grades Dr. sc. nat. Technische Hochschule Ilmenau, 1985

[67] Stiebitz M., “Subgraphs of colour-critical graphs”, Combinatorica, 7:3 (1987), 303–312 | DOI | MR | Zbl

[68] Stockmeyer L. J., “Planar 3-colorability is NP-complete”, SIGACT News, 51:3 (1973), 19–25 | DOI

[69] Thomassen C., “Five-coloring graphs on the torus”, J. Combin. Theory. Ser. B, 62:1 (1994), 11–33 | DOI | MR | Zbl

[70] Thomassen C., “Color-critical graphs on a fixed surface”, J. Combin. Theory. Ser. A, 70:1 (1997), 67–100 | DOI | MR | Zbl

[71] Toft B., “On the maximal number of edges of critical $k$-chromatic graphs”, Studia Sci. Math. Hungar., 5:3–4 (1970), 461–470 | MR

[72] Toft B., “Two theorems on critical 4-chromatic graphs”, Studia Sci. Math. Hungar., 7:1–2 (1972), 83–89 | MR | Zbl

[73] Toft B., “Color-critical graphs and hypergraphs”, J. Combin. Theory, 16:2 (1974), 145–161 | DOI | MR | Zbl

[74] Toft B., “On critical sugraphs of color-critical graphs”, Discrete Math., 7:3 (1974), 377–392 | DOI | MR | Zbl

[75] Weinstein J., “Excess in critical graphs”, J. Combin. Theory. Ser. B, 18:1 (1975), 24–31 | DOI | MR | Zbl

[76] Youngs D. A., “Gallai's problem on Dirac's construction”, Discrete Math., 101:1–3 (1992), 343–350 | DOI | MR | Zbl