Colouring graphs when the number of colours is almost the maximum degree. (English) Zbl 1301.05130
Summary: We consider the chromatic number of graphs with maximum degree \(\Delta\). For sufficiently large \(\Delta\), we determine the precise values of \(k\) for which the barrier to \((\Delta +1-k)\)-colourability must be a local condition, i.e. a small subgraph. We also show that for \(\Delta\) constant and sufficiently large, \((\Delta +1-k)\)-colourability is either NP-complete or can be solved in linear time, and we determine precisely which values of \(k\) correspond to each case.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C07 | Vertex degrees |
| 05C35 | Extremal problems in graph theory |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Azuma, K., Weighted sums of certain dependent random variables, Tohoku Math. J., 19, 357-367 (1967) · Zbl 0178.21103 |
| [2] | Beck, J., An algorithmic approach to the Lovasz Local Lemma, Random Structures Algorithms, 2, 343-365 (1991) · Zbl 0756.05080 |
| [3] | Beutelspacher, A.; Hering, P., Minimal graphs for which the chromatic number equals the maximal degree, Ars Combin., 18, 201-216 (1984) · Zbl 0554.05025 |
| [4] | Borodin, O.; Kostochka, A., On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density, J. Combin. Theory Ser. B, 23, 247-250 (1977) · Zbl 0336.05104 |
| [5] | Brooks, R., On colouring the nodes of a network, Proc. Cambridge Philos. Soc., 37, 194-197 (1941) · Zbl 0027.26403 |
| [6] | Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statist., 23, 493-509 (1952) · Zbl 0048.11804 |
| [7] | Edmonds, J., Paths, stars and flowers, Canad. J. Math., 17, 449-467 (1965) · Zbl 0132.20903 |
| [8] | Embden-Weinert, S.; Hougardy, S.; Kreuter, B., Uniquely colourable graphs and the hardness of colouring graphs of large girth, Combin. Probab. Comput., 7, 375-386 (1998) · Zbl 0918.05051 |
| [9] | Erdős, P., Graph theory and probability, Canad. J. Math., 11, 34-38 (1959) · Zbl 0084.39602 |
| [10] | Erdős, P.; Lovász, L., Problems and results on 3-chromatic hypergraphs and some related questions, (Hajnal, A.; etal., Infinite and Finite Sets. Infinite and Finite Sets, Colloq. Math. Soc. J. Bolyai, vol. 11 (1975), North-Holland: North-Holland Amsterdam), 609-627 · Zbl 0315.05117 |
| [11] | Farzad, B., When the chromatic number is close to the maximum degree (2001), Dept. of Computer Science, University of Toronto, MSc thesis |
| [12] | Farzad, B.; Molloy, M.; Reed, B., \((\Delta - k)\)-critical graphs, J. Combin. Theory Ser. B, 93, 173-185 (2005) · Zbl 1062.05056 |
| [13] | Hoeffding, W., Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., 58, 713-721 (1963) · Zbl 0127.10602 |
| [14] | Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, J. Comput. System Sci., 63, 512-530 (2001) · Zbl 1006.68052 |
| [15] | McDiarmid, C., Concentration for independent permutations, Combin. Probab. Comput., 11, 163-178 (2002) · Zbl 1001.60014 |
| [16] | Molloy, M.; Reed, B., Colouring graphs whose chromatic number is near their maximum degree, (Proceedings of Latin American Theoretical Informatics (1998)) · Zbl 0918.05053 |
| [17] | Molloy, M.; Reed, B., Colouring graphs when the number of colours is almost the maximum degree, (Proceedings of the 33rd ACM Symposium on Theory of Computing (2001)), 462-470 · Zbl 1323.05052 |
| [18] | Molloy, M.; Reed, B., Graph Colouring and the Probabilistic Method (2002), Springer · Zbl 0987.05002 |
| [19] | Moser, R., A constructive proof of the Lovasz Local Lemma, (Proceedings of the 41st ACM Symposium on Theory of Computing (2009)) · Zbl 1304.68079 |
| [21] | Reed, B., \(ω\), Δ, and \(χ\), J. Graph Theory, 27, 177-212 (1998) · Zbl 0980.05026 |
| [22] | Talagrand, M., Concentration of measure and isoperimetric inequalities in product spaces, Inst. Hautes Études Sci. Publ. Math., 81, 73-205 (1995) · Zbl 0864.60013 |
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.
