Extremal decompositions for Nordhaus-Gaddum theorems. (English) Zbl 1514.05056
Summary: A Nordhaus-Gaddum theorem states bounds on \(p(G) + p(\overline{G})\) and \(p(G) \cdot p (\overline{G})\) for some graph parameter \(p(G)\). We consider the sum upper bound for degeneracy, chromatic number, fractional and circular chromatic number, list chromatic number, span (for \(L (2, 1)\) labeling), and point partition number. Viewing \(\{G, \overline{G}\}\) as a decomposition of \(K_n\), we describe a strategy to determine the extremal decompositions for these parameters. This produces short proofs of several existing results as well as several new theorems.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C78 | Graph labelling (graceful graphs, bandwidth, etc.) |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
Nordhaus-Gaddum; chromatic number; list coloring; degeneracy; \(L(2, 1)\) labeling; point partition numberReferences:
| [1] | Aouchiche, M.; Hansen, P., A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math., 161, 4-5, 466-546 (2013) · Zbl 1259.05083 |
| [2] | Balakrishnan, H.; Deo, N., Parallel algorithm for radiocoloring a graph, Congr. Numer., 160, 193-204 (2003) · Zbl 1040.05011 |
| [3] | Bickle, A., Nordhaus-Gaddum theorems for k-decompositions, Congr. Numer., 211, 171-183 (2012) · Zbl 1278.05151 |
| [4] | Bickle, A., Cores and shells of graphs, Math. Bohem., 138, 1, 43-59 (2013) · Zbl 1274.05399 |
| [5] | Bickle, A., A short proof of Brooks’ Theorem for vertex arboricity, AKCE Int. J. Graphs Comb., 419-421 (2020) · Zbl 1473.05236 |
| [6] | Bickle, A., Fundamentals of Graph Theory (2020), AMS · Zbl 1443.05001 |
| [7] | A. Bickle, A survey of maximal k-degenerate graphs and k-trees, 2021, submitted for publication. · Zbl 1459.05048 |
| [8] | Bickle, A.; White, A., Nordhaus-Gaddum results for genus, Discrete Math., 313, 6, 824-829 (2013) · Zbl 1260.05040 |
| [9] | Borodin, O. V., Criterion of chromaticity of a degree prescription, (Abstracts of IV All-Union Conference on Theoretical Cybernetics. Abstracts of IV All-Union Conference on Theoretical Cybernetics, Novosibirsk (1977)), 127-128, (in Russian) |
| [10] | Borodin, O. V., Bidegree of graph and degeneracy number, Mat. Zametki, 53, 4, 13-20 (1993) · Zbl 0795.05080 |
| [11] | Brooks, R. L., On colouring the nodes of a network, Math. Proc. Camb. Philos. Soc., 37, 194-197 (1941) · Zbl 0027.26403 |
| [12] | Brown, J. I.; Hoshino, R., Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers, Discrete Math., 309, 2223-2232 (2009) · Zbl 1198.05039 |
| [13] | Chartrand, G.; Kronk, H. V., The point-arboricity of planar graphs, J. Lond. Math. Soc., 44, 612-616 (1969) · Zbl 0175.50505 |
| [14] | Chartrand, G.; Mitchem, J., Graphical theorems of the Nordhaus-Gaddum class, (Recent Trends in Graph Theory. Recent Trends in Graph Theory, Lecture Notes in Mathematics, vol. 186 (1971)), 55-61 · Zbl 0211.56702 |
| [15] | Chartrand, G.; Zhang, P., Chromatic Graph Theory (2009), CRC Press · Zbl 1169.05001 |
| [16] | Cheng, C.; Collins, K. L.; Trenk, A. N., Split graphs and Nordhaus-Gaddum graphs, Discrete Math., 339, 2345-2356 (2016) · Zbl 1338.05046 |
| [17] | Collins, K. L.; Trenk, A. N., Nordhaus-Gaddum theorem for the distinguishing chromatic number, Electron. J. Comb., 20, 3, Article P46 pp. (2013) · Zbl 1298.05112 |
| [18] | Cranston, D. W.; Rabern, L., Brooks’ theorem and beyond, J. Graph Theory, 80, 3, 199-225 (2015) · Zbl 1330.05061 |
| [19] | Dantas, S.; Gravier, S.; Maffray, F., Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum, Discrete Appl. Math., 141, 93-101 (2004) · Zbl 1043.05044 |
| [20] | Erdős, P.; Hajnal, A., On chromatic numbers of graphs and set systems, Acta Math. Acad. Sci. Hung., 17, 61-99 (1966) · Zbl 0151.33701 |
| [21] | Erdős, P.; Rubin, A.; Taylor, H., Choosability in graphs, Congr. Numer., 26, 125-157 (1979) · Zbl 0469.05032 |
| [22] | Finck, H. J., On the chromatic numbers of a graph and its complement, (Theory of Graphs. Theory of Graphs, Proc. Colloq., Tihany, 1966 (1968), Academic Press: Academic Press New York), 99-113 · Zbl 0157.55201 |
| [23] | Furedi, Z.; Kostochka, A.; Stiebitz, M.; Skrekovski, R.; West, D., Nordhaus-Gaddum-type theorems for decompositions into many parts, J. Graph Theory, 50, 273-292 (2005) · Zbl 1078.05068 |
| [24] | Gravier, S.; Maffray, F., Graphs whose choice number is equal to their chromatic number, J. Graph Theory, 27, 87-97 (1998) · Zbl 0891.05031 |
| [25] | Gravier, S.; Maffray, F.; Mohar, B., On a list-coloring problem, Discrete Math., 268, 1-3, 303-308 (2003) · Zbl 1018.05028 |
| [26] | Griggs, J. R.; Yeh, R. K., Labelling graphs with a condition at distance two, SIAM J. Discrete Math., 5, 586-595 (1992) · Zbl 0767.05080 |
| [27] | Kronk, H. V.; Mitchem, J., Critical point arboritic graphs, J. Lond. Math. Soc., 9, 459-466 (1974/1975) · Zbl 0298.05132 |
| [28] | Lick, D. R.; White, A. T., k-degenerate graphs, Can. J. Math., 22, 1082-1096 (1970) · Zbl 0202.23502 |
| [29] | Lick, D. R.; White, A. T., Point-partition numbers of complementary graphs, Sci. Math. Jpn., 19, 233-237 (1974) · Zbl 0305.05123 |
| [30] | Mitchem, J., On the point-arboricity of a graph and its complement, Can. J. Math., 23, 287-292 (1971) · Zbl 0194.25104 |
| [31] | Mitchem, J., An extension of Brooks’ theorem to n-degenerate graphs, Discrete Math., 17, 291-298 (1977) · Zbl 0351.05124 |
| [32] | Nordhaus, E. A.; Gaddum, J., On complementary graphs, Am. Math. Mon., 63, 175-177 (1956) · Zbl 0070.18503 |
| [33] | Simões-Pereira, J. M.S., A survey of k-degenerate graphs, Graph Theory Newsl., 5, 1-7 (1976) · Zbl 0331.05135 |
| [34] | Starr, C. L.; Turner, G. E., Complementary graphs and the chromatic number, Missouri J. Math. Sci., 20, 1, 19-26 (2008) · Zbl 1145.05309 |
| [35] | Szekeres, G.; Wilf, H., An inequality for the chromatic number of a graph, J. Comb. Theory, 4, 1-3 (1968) · Zbl 0171.44901 |
| [36] | Vizing, V. G., Vertex colorings with given colors, Diskretn. Anal., 29, 3-10 (1976), (in Russian) · Zbl 0362.05060 |
| [37] | West, D., Combinatorial Mathematics (2020), Cambridge University Press |
| [38] | Zhu, X., Circular chromatic number: a survey, Discrete Math., 229, 371-410 (2001) · Zbl 0973.05030 |
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.
