The existence of uniquely \(-G\) colourable graphs. (English) Zbl 0885.05062
Given graphs \(F\) and \(G\) and a nonnegative integer \(k\), a function \(\pi :V(F)\rightarrow \{1,\ldots ,k\}\) is a \(-G\) \(k\)-colouring of \(F\) if no induced copy of \(G\) is monochromatic; \(F\) is \(-G\) \(k\)-chromatic if \(F\) has a \(-G\) \(k\)-colouring but no \(-G\) \((k-1)\)-colouring. Further, we say \(F\) is uniquely \(-G\) \(k\)-colourable if \(G\) is \(-G\) \(k\)-chromatic and, up to a permutation of colours, it has only one \(-G\) \(k\)-colouring. It was conjectured by J. I. Brown and D. G. Corneil [J. Graph Theory 11, 87-99 (1987; Zbl 0608.05035)] that uniquely \(-G\) \(k\)-colourable graphs exist for all graphs \(G\) of order at least 2 and all positive integers \(k\). What has been known so far is that the conjecture holds whenever \(G\) or its complement has a universal vertex or is 2-connected. In this paper the conjecture is completely settled by showing that, in fact, in all cases infinitely many such graphs exist.
Reviewer: I.Tomescu (Bucureşti)
Citations:
Zbl 0608.05035References:
| [1] | D. Achlioptas, The complexity of \(G\); D. Achlioptas, The complexity of \(G\) · Zbl 0904.05030 |
| [2] | Albertson, M. O.; Jamison, R. E.; Hedetniemi, S. T.; Locke, S. C., The subchromatic number of a graph, Discrete. Math., 74, 33-49 (1989) · Zbl 0681.05033 |
| [3] | Benadé, G.; Broere, I.; Brown, J. I., A construction of uniquely \(C_4\)-free colourable graphs, Quaestiones Math., 13, 259-264 (1990) · Zbl 0725.05042 |
| [4] | Berge, C., Graphs and Hypergraphs (1979), North Holland: North Holland New York · Zbl 0483.05029 |
| [5] | Bollobás, B., Random Graphs (1985), Academic Press: Academic Press London · Zbl 0567.05042 |
| [6] | Bollobás, B.; Sauer, N., Uniquely colourable graphs with large girth, Canad. J. Math., 28, 1340-1344 (1970) · Zbl 0344.05115 |
| [7] | Bollobás, B.; Thomason, A. G., Uniquely partitionable graphs, J. London Math. Soc., 16, 403-410 (1977) · Zbl 0377.05038 |
| [8] | Borowiecki, M.; Mihók, P., On \((n,P)\)-partitionable graphs, (Graphs, Hypergraphs and Applications (1985), Teubner-Texte: Teubner-Texte Leipzig), 15-18 · Zbl 0628.05033 |
| [9] | Broere, I.; Mynhardt, C., Generalized colorings of outerplanar and planar graphs, (Alavi, Y.; etal., Graph Theory with Applications to Algorithms and Computer Science (1985), Wiley: Wiley New York), 151-161 · Zbl 0571.05017 |
| [10] | Brown, J. I., A theory of generalized graph colourings, (Ph. D. Thesis (1987), Department of Mathematics, University of Toronto) |
| [11] | Brown, J. I., The complexity of generalized graph coloring problems, Discrete. Appl. Math., 69, 245-253 (1996) |
| [12] | Brown, J. I.; Corneil, D. G., On generalized graph colorings, J. Graph Theory, 11, 87-99 (1987) · Zbl 0608.05035 |
| [13] | Brown, J. I.; Corneil, D. G., Perfect colourings, Ars Combin., 30, 141-159 (1990) · Zbl 0728.05022 |
| [14] | Brown, J. I.; Corneil, D. G., Graph properties and hypergraph colourings, Discrete Math., 98, 81-93 (1991) · Zbl 0768.05039 |
| [15] | Brown, J. I.; Corneil, D. G., On uniquely −\(Gk\)-colourable graphs, Quaestiones Math., 15, 477-487 (1992) · Zbl 0771.05033 |
| [16] | Brown, J. I.; Rödl, V., A new construction of \(k\)-Folkman graphs, Ars Combin., 29, 265-269 (1990) · Zbl 0731.05020 |
| [17] | Brown, J. I.; Rödl, V., A Ramsey type problem concerning vertex colourings, J. Combin. Theory B, 52, 45-52 (1991) · Zbl 0686.05039 |
| [18] | Brown, J. I.; Rödl, V., Folkman numbers for graphs of small order, Ars Combin. A, 35, 11-27 (1993) · Zbl 0840.05062 |
| [19] | Cockayne, E. J., Colour classes for \(r\)-graphs, Canad. Math. Bull., 15, 349-354 (1972) · Zbl 0254.05106 |
| [20] | Folkman, J., Graphs with monochromatic complete subgraphs in every edge coloring, SIAM J. Appl. Math., 18, 19-24 (1970) · Zbl 0193.53103 |
| [21] | Grossman, J. W., Graphs with unique Ramsey colourings, J. Graph Theory, 7, 85-90 (1983) · Zbl 0512.05043 |
| [22] | Harary, F., Conditional colorability of graphs, (Harary, F.; Maybee, J., Graphs and Applications. Graphs and Applications, Proc. 1st Col. Symp. Graph Theory (1985), Wiley: Wiley New York), 127-136 · Zbl 0556.05027 |
| [23] | Hedetniemi, S., On partitioning planar graphs, Canad. Math. Bull., 11, 203-211 (1968) · Zbl 0167.21805 |
| [24] | Komjath, P.; Rödl, V., Coloring of universal graphs, Discrete. Math., 63, 55-60 (1986) · Zbl 0589.05053 |
| [25] | Mynhardt, C. M.; Broere, I., Generalized colourings of graphs, (Alavi, Y.; etal., Graph Theory with Applications to Algorithms and Computer Science (1985), Wiley: Wiley New York), 583-594 · Zbl 0571.05017 |
| [26] | Nešetřil, J.; Rödl, V., Partitions of vertices, Comm. Math. Univ. Carolinae, 17, 85-95 (1976) · Zbl 0344.05150 |
| [27] | Nešetřil, J.; Rödl, V., The Ramsey property for graphs with forbidden complete subgraphs, J. Combin. Theory. B, 20, 243-249 (1976) · Zbl 0329.05115 |
| [28] | Nešetřil, J.; Rödl, V., On Ramsey graphs without cycles of short odd length, Comm. Math. Univ. Carolinae, 20, 565-582 (1979) · Zbl 0425.05025 |
| [29] | Sampathkumar, E.; Venkatachalam, C. V., Chromatic partitions of a graph, Discrete. Math., 74, 227-239 (1989) · Zbl 0688.05028 |
| [30] | West, D. B., Open Problems, SIAM Activity Group Discrete Math. Newsletter, 5, 2, 8-9 (1995) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
