×

Extremal colorings and independent sets. (English) Zbl 1402.05064

Summary: We consider several extremal problems of maximizing the number of colorings and independent sets in some graph families with fixed chromatic number and order. First, we address the problem of maximizing the number of colorings in the family of connected graphs with chromatic number \(k\) and order \(n\) where \(k\geq 4\). It was conjectured that extremal graphs are those which have clique number \(k\) and size \(\binom{k}{2}+n-k\). We affirm this conjecture for 4-chromatic claw-free graphs and for all \(k\)-chromatic line graphs with \(k\geq 4\). We also reduce this extremal problem to a finite family of graphs when restricted to claw-free graphs. Secondly, we determine the maximum number of independent sets of each size in the family of \(n\)-vertex \(k\)-chromatic graphs (respectively connected \(n\)-vertex \(k\)-chromatic graphs and \(n\)-vertex \(k\)-chromatic graphs with \(c\) components). We show that the unique extremal graph is \(K_k\cup E_{n-k}\), \(K_1\vee (K_{k-1}\cup E_{n-k})\) and \((K_1 \vee (K_{k-1} \cup E_{n-k-c+1}))\cup E_{c-1}\) respectively.

MSC:

05C15 Coloring of graphs and hypergraphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory

References:

[1] Alexander, J., Cutler, J., Mink, T.: Independent sets in graphs with given minimum degree. Electron. J. Combin. 19(3), #P37 (2012) · Zbl 1252.05157
[2] Brown, J., Erey, A.: New bounds for chromatic polynomials and chromatic roots. Discrete Math. 338(11), 1938-1946 (2015) · Zbl 1314.05061 · doi:10.1016/j.disc.2015.04.021
[3] Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164(1), 51-229 (2006) · Zbl 1112.05042 · doi:10.4007/annals.2006.164.51
[4] Cutler, J.: Coloring graphs with graphs: a survey. Graph Theory Notes N.Y. 63, 7-16 (2012)
[5] Cutler, J., Radcliffe, A.J.: Extremal problems for independent set enumeration. Electron. J. Combin. 18(1), #P169 (2011) · Zbl 1229.05138
[6] Davies, E., Jenssen, M., Perkins, W., Roberts, B.: Extremes of the internal energy of the Potts model on cubic graphs. Random Struct. Algorithms 53(1), 59-75 (2018). arXiv:1610.08496 · Zbl 1401.05108 · doi:10.1002/rsa.20767
[7] Dong, F.M., Koh, K.M., Teo, K.L.: Chromatic Polynomials and Chromaticity of Graphs. World Scientific, London (2005) · Zbl 1070.05038 · doi:10.1142/5814
[8] Engbers, J.: Extremal \[HH\]-colorings of graphs with fixed minimum degree. J. Graph Theory 79, 103-124 (2015) · Zbl 1320.05038 · doi:10.1002/jgt.21820
[9] Engbers, J.: Maximizing \[HH\]-colorings of connected graphs with fixed minimum degree. J. Graph Theory 85, 780-787 (2017) · Zbl 1368.05049 · doi:10.1002/jgt.22105
[10] Engbers, J., Galvin, D.: Extremal \[HH\]-colorings of trees and 2-connected graphs. J. Combin. Theory Ser. B 122, 800-814 (2017) · Zbl 1350.05033 · doi:10.1016/j.jctb.2016.09.009
[11] Erey, A.: On the maximum number of colorings of a graph. J. Combin. 9(3), 489-497 (2018). arXiv:1610.07208 · Zbl 1387.05087 · doi:10.4310/JOC.2018.v9.n3.a4
[12] Erey, A.: Maximizing the number of \[x\] x-colorings of \[44\]-chromatic graphs. Discrete Math. 341(5), 1419-1431 (2018). https://doi.org/10.1016/j.disc.2017.09.028 · Zbl 1383.05099 · doi:10.1016/j.disc.2017.09.028
[13] Faudree, R.J., Gould, R.J., Jacobson, M.S.: Minimum degree and disjoint cycles in claw-free graphs. Combin. Probab. Comput. 21, 129-139 (2012) · Zbl 1241.05094 · doi:10.1017/S0963548311000708
[14] Fox, J., He, X., Manners, F.: A proof of Tomescu’s graph coloring conjecture. arXiv:1712.06067 · Zbl 1414.05114
[15] Galvin, D.: Maximizing \[HH\]-colorings of regular graphs. J. Graph Theory 73, 66-84 (2013) · Zbl 1262.05052 · doi:10.1002/jgt.21658
[16] Galvin, D.: Counting colorings of a regular graph. Graphs Combin. 31, 629-638 (2015) · Zbl 1312.05049 · doi:10.1007/s00373-013-1403-z
[17] Galvin, David; Tetali, Prasad, On weighted graph homomorphisms, 97-104 (2004), Providence, Rhode Island · Zbl 1061.05068
[18] Guggiari, H., Scott, A.: Maximising \[HH\]-colourings of graphs. arXiv:1611.02911 · Zbl 1425.05056
[19] Knox F., Mohar, B.: Maximum number of colourings. I. 4-chromatic graphs. arXiv:1708.01781 · Zbl 1443.05070
[20] Knox, F., Mohar, B.: Maximum number of colourings. II. 5-chromatic graphs. arXiv: 1710.06535 · Zbl 1419.05077
[21] Li, S., Liu, L., Wu, Y.: On the coefficients of the independence polynomial of graphs. J. Combin. Optim. 33, 1324-1342 (2017) · Zbl 1369.05163 · doi:10.1007/s10878-016-0037-5
[22] Loh, P.-S., Pikhurko, O., Sudakov, B.: Maximizing the number of \[q\] q-colorings. Proc. Lond. Math. Soc. 101, 655-696 (2010) · Zbl 1221.05152 · doi:10.1112/plms/pdp041
[23] Ma, J., Naves, H.: Maximizing proper colorings on graphs. J. Combin. Theory Ser. B 115, 236-275 (2015) · Zbl 1319.05054 · doi:10.1016/j.jctb.2015.07.002
[24] Merrifield, R., Simmons, H.: Topological Methods in Chemistry. Wiley, New York (1989)
[25] Prodinger, H., Tichy, R.: Fibonacci numbers of graphs. Fibonacci Q. 20, 16-21 (1982) · Zbl 0475.05046
[26] Tomescu, I.: Le nombre des graphes connexes k-chromatiques minimaux aux sommets étiquetés. C. R. Acad. Sci. Paris 273, 1124-1126 (1971) · Zbl 0223.05115
[27] Tomescu, I.: Le nombre maximal de 3-colorations dun graphe connnexe. Discrete Math. 1, 351-356 (1972) · Zbl 0226.05115 · doi:10.1016/0012-365X(72)90042-8
[28] Tomescu, I.: Introduction to Combinatorics. Collets (Publishers) Ltd., London (1975)
[29] Tomescu, I.: Maximal chromatic polynomials of connected planar graphs. J. Graph Theory 14, 101-110 (1990) · Zbl 0702.05033 · doi:10.1002/jgt.3190140111
[30] Wingard, G.: Properties and Applications of the Fibonacci Polynomial of a Graph, Ph.D. thesis. University of Mississippi, Oxford (1995)
[31] Xu, K.: On the Hosoya index and the Merrifield-Simmons index of graphs with a given clique number. Appl. Math. Lett. 23, 395-398 (2010) · Zbl 1218.05073 · doi:10.1016/j.aml.2009.11.005
[32] Zhao, Y.: Extremal regular graphs: independent sets and graph homomorphisms. Amer. Math. Mon. 124, 827-843 (2017). arXiv:1610.09210 · Zbl 1391.05142 · doi:10.4169/amer.math.monthly.124.9.827
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.