On the generalized \(\vartheta\)-number and related problems for highly symmetric graphs. (English) Zbl 1494.05048
Summary: This paper is an in-depth analysis of the generalized \(\vartheta\)-number of a graph. The generalized \(\vartheta\)-number, \(\vartheta_k(G)\), serves as a bound for both the \(k\)-multichromatic number of a graph and the maximum \(k\)-colorable subgraph problem. We present various properties of \(\vartheta_k(G)\), such as that the sequence \((\vartheta_k(G))_k\) is increasing and bounded from above by the order of the graph \(G\). We study \(\vartheta_k(G)\) when \(G\) is the strong, disjunction, or Cartesian product of two graphs. We provide closed form expressions for the generalized \(\vartheta\)-number on several classes of graphs including the Kneser graphs, cycle graphs, strongly regular graphs, and orthogonality graphs. Our paper provides bounds on the product and sum of the \(k\)-multichromatic number of a graph and its complement graph, as well as lower bounds for the \(k\)-multichromatic number on several graph classes including the Hamming and Johnson graphs.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05E30 | Association schemes, strongly regular graphs |
| 05C76 | Graph operations (line graphs, products, etc.) |
| 90C35 | Programming involving graphs or networks |
Keywords:
\(k\)-multicoloring; \(k\)-colorable subgraph problem; generalized \(\vartheta\)-number; Johnson graphs; Hamming graphs; strongly regular graphsReferences:
| [1] | H. Abdo and D. Dimitrov, The total irregularity of graphs under graph operations, Miskolc Math. Notes, 15 (2014), pp. 3-17. · Zbl 1313.05313 |
| [2] | L. Addario-Berry, W. Kennedy, A. D. King, Z. Li, and B. Reed, Finding a maximum-weight induced \(k-\) partite subgraph of an \(i-\) triangulated graph, Discrete Appl. Math., 158 (2010), pp. 765-770. · Zbl 1216.05152 |
| [3] | F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim., 5 (1995), pp. 13-51. · Zbl 0833.90087 |
| [4] | M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math., 161 (2013), pp. 466-546. · Zbl 1259.05083 |
| [5] | K. Appel and W. Haken, Every planar map is four colorable. Part I: Discharging, Illinois J. Math., 21 (1977), pp. 429-490. · Zbl 0387.05009 |
| [6] | C. Bachoc, A. Pêcher, and A. Thiéry, On the theta number of powers of cycle graphs, Combinatorica, 33 (2013), pp. 297-317. · Zbl 1349.05100 |
| [7] | Z. Baranyai, On the factorization of the complete uniform hypergraphs, in Infinite and Finite sets, A. Hajnal, R. Rado and V.T. Sós, eds., Bolyai J. Mat. Társulat, Budapest, 1975, pp. 91-108. · Zbl 0306.05137 |
| [8] | F. Boesch and R. Tindell, Circulants and their connectivities, J. Graph Theory, 8 (1984), pp. 487-499. · Zbl 0549.05048 |
| [9] | R. C. Brigham and R. D. Dutton, Generalized \(k\)-tuple colorings of cycles and other graphs, J. Combin. Theory Ser. B, 32 (1982), pp. 90-94. · Zbl 0465.05032 |
| [10] | V. E. Brimkov, Algorithmic and explicit determination of the Lovász number for certain circulant graphs, Discrete Appl. Math., 155 (2007), pp. 1812-1825. · Zbl 1123.05085 |
| [11] | V. E. Brimkov, B. Codenotti, V. Crespi, and M. Leoncini, On the Lovász number of certain circulant graphs, in Proceedings of the 4th Italian Conference on Algorithms and Complexity, G. C. Bongiovanni, G. Gambosi, and R. Petreschi, eds., Lecture Notes in Comput. Sci. 1767, Springer, New York, 2000, pp. 291-305. · Zbl 0955.05097 |
| [12] | A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989. · Zbl 0747.05073 |
| [13] | A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, New York, 2011. · Zbl 1231.05001 |
| [14] | M. Campêlo, R. C. Corrêa, P. F. Moura, and M. C. Santos, On optimal \(k\)-fold colorings of webs and antiwebs, Discrete Appl. Math., 161 (2013), pp. 60-70. · Zbl 1296.05068 |
| [15] | M. Campêlo, P. F. Moura, and M. C. Santos, Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope, Discrete Optim., 21 (2016), pp. 131-156. · Zbl 1387.05082 |
| [16] | G. J. Chaitin, Register allocation and spilling via graph coloring, ACM SIGPLAN Notices, 17 (1982), pp. 98-101. |
| [17] | T. H. Chan, K. L. Chang, and R. Raman, An SDP primal-dual algorithm for approximating the Lovász-theta function, in Proceedings of the International Symposium on Information Theory, Korea, IEEE, 2009, pp. 2808-2812. |
| [18] | L.-C. Chang, The uniqueness and nonuniqueness of the triangular association scheme, Science Record, 3 (1959), pp. 604-613. · Zbl 0089.15102 |
| [19] | B.-L. Chen and K.-W. Lih, Hamiltonian uniform subset graphs, J. Combin. Theory Ser. B, 42 (1987), pp. 257-263. · Zbl 0585.05021 |
| [20] | V. Chvátal, Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math., 4 (1973), pp. 305-337. · Zbl 0253.05131 |
| [21] | D. W. Cranston and L. Rabern, Planar graphs are 9/2-colorable, J. Combin. Theory Ser. B, 133 (2018), pp. 32-45. · Zbl 1397.05061 |
| [22] | V. Crespi, Exact formulae for the Lovász theta function of sparse circulant graphs, SIAM J. Discrete Math., 17 (2004), pp. 670-674. · Zbl 1056.05038 |
| [23] | E. de Klerk and D. V. Pasechnik, A note on the stability number of an orthogonality graph, European J. Combin., 28 (2007), pp. 1971-1979. · Zbl 1125.05053 |
| [24] | S. Y. El Rouayheb, C. N. Georghiades, E. Soljanin, and A. Sprintson, Bounds on codes based on graph theory, in Proceedings of the International Symposium on Information Theory, Nice, France, IEEE, 2007, pp. 1876-1879. |
| [25] | P. Fouilhoux and A. R. Mahjoub, Solving VLSI design and DNA sequencing problems using bipartization of graphs, Comput. Optim. Appl., 51 (2012), pp. 749-781. · Zbl 1245.90100 |
| [26] | P. Frankl, Orthogonal vectors in the \(n\)-dimensional cube and codes with missing distances, Combinatorica, 6 (1986), pp. 279-285. · Zbl 0648.05031 |
| [27] | P. Frankl and V. Rödl, Forbidden intersections, Trans. Amer. Math. Soc., 300 (1987), pp. 259-286. · Zbl 0611.05002 |
| [28] | P. Frankl and N. Tokushige, The Erdös-Ko-Rado theorem for integer sequences, Combinatorica, 19 (1999), pp. 55-63. · Zbl 0959.05115 |
| [29] | Z. Füredi and P. Frankl, Extremal problems concerning Kneser graphs, J. Combin. Theory Ser. B, 40 (1986), pp. 270-284. · Zbl 0564.05002 |
| [30] | V. Galliard, Classical Pseudo Telepathy and Coloring Graphs, Diploma thesis, ETH Zurich, 2001. |
| [31] | V. Galliard, A. Tapp, and S. Wolf, The impossibility of pseudotelepathy without quantum entanglement, in Proceedings of the IEEE International Symposium on Information Theory, Yokohama, Japan, IEEE, 2003, p. 457. |
| [32] | R. Gandhi, M. M. Halldórsson, G. Kortsarz, and H. Shachnai, Improved bounds for sum multicoloring and scheduling dependent jobs with minsum criteria, in International Workshop on Approximation and Online Algorithms, Springer, New York, 2004, pp. 68-82. · Zbl 1124.90323 |
| [33] | K. Gatermann and P. Parrilo, Symmetry groups, semidefinite programs, and sums of squares, J. Pure Appl. Algebra, 192 (2004), pp. 95-128. · Zbl 1108.13021 |
| [34] | D. Geller and S. Stahl, The chromatic number and other functions of the lexicographic product, J. Combin. Theory Ser. B, 19 (1975), pp. 87-95. · Zbl 0282.05114 |
| [35] | C. D. Godsil and M. W. Newman, Coloring an orthogonality graph, SIAM J. Discrete Math., 22 (2008), pp. 683-692. · Zbl 1167.05314 |
| [36] | C. D. Godsil and M. W. Newman, Eigenvalue bounds for independent sets, J. Combin. Theory Ser. B, 98 (2008), pp. 721-734. · Zbl 1156.05041 |
| [37] | D. Greenwell and L. Lovász, Applications of product colouring, Acta Math. Hungar., 25 (1974), pp. 335-340. · Zbl 0294.05108 |
| [38] | M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1 (1981), pp. 169-197. · Zbl 0492.90056 |
| [39] | N. Gvozdenović, Approximating the Stability Number and the Chromatic Number of a Graph via Semidefinite Programming, Ph.D. thesis, Universiteit van Amsterdam, 2008. · Zbl 1213.05081 |
| [40] | N. Gvozdenović and M. Laurent, The operator \({\Psi}\) for the chromatic number of a graph, SIAM J. Optim., 19 (2008), pp. 572-591. · Zbl 1213.05080 |
| [41] | W. H. Haemers, Eigenvalue Techniques in Design and Graph Theory, Ph.D. thesis, Math. Centr. Tract 121 (Amsterdam, 1980), Reidel, Dordrecht, 1980. · Zbl 0429.05013 |
| [42] | W. H. Haemers, An upper bound for the Shannon capacity of a graph, Colloq. Math. Soc. János Bolyai, 25 (1978), pp. 267-272. · Zbl 0474.94021 |
| [43] | M. M. Halldórsson and G. Kortsarz, Multicoloring: Problems and techniques, in Mathematical Foundations of Computer Science 2004, J. Fiala, V. Koubek, and J. Kratochvíl, eds., Springer, Berlin, 2004, pp. 25-41. · Zbl 1096.68684 |
| [44] | S. T. Hedetniemi, Homomorphisms of Graphs and Automata, Tech. report, Communication Sciences, University of Michigan, Ann Arbor, 1966. |
| [45] | A. Hilton, R. Rado, and S. Scott, A \((< 5)\)-colour theorem for planar graphs, Bull. Lond. Math. Soc., 5 (1973), pp. 302-306. · Zbl 0278.05103 |
| [46] | A. Hoffman, On eigenvalues and colorings of graphs, in Graph Theory and Its Applications, B. Harris, ed., Academic Press, New York, 1970, pp. 79-91. · Zbl 0221.05061 |
| [47] | R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, Cambridge, UK, 1994. · Zbl 0801.15001 |
| [48] | F. Ihringer and H. Tanaka, The independence number of the orthogonality graph in dimension \(2^k\), Combinatorica, 39 (2019), pp. 1425-1428. · Zbl 1449.05201 |
| [49] | S. Klavžar, Coloring graph products-a survey, Discrete Math., 155 (1996), pp. 135-145. · Zbl 0857.05035 |
| [50] | M. Kneser, Aufgabe 300, jahresbericht, Deutschen Math. Ver., 58 (1955). |
| [51] | D. E. Knuth, The sandwich theorem, Electron. J. Combin., 1 (1994). · Zbl 0810.05065 |
| [52] | A. Koster and M. Scheffel, A routing and network dimensioning strategy to reduce wavelength continuity conflicts in all-optical networks, in Proceedings of INOC 2007, Belgium, 2007. |
| [53] | O. Kuryatnikova, R. Sotirov, and J. C. Vera, The maximum \(k\)-colorable subgraph problem and related problems, INFORMS J. Comput., 34 (2022). · Zbl 07549399 |
| [54] | J. Lewis and M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci., 20 (1980), pp. 219-230. · Zbl 0436.68029 |
| [55] | W. Lin, Multicoloring and Mycielski construction, Discrete Math., 308 (2008), pp. 3565-3573. · Zbl 1162.05022 |
| [56] | W. Lin, D. D.-F. Liu, and X. Zhu, Multi-coloring the Mycielskian of graphs, J. Graph Theory, 63 (2010), pp. 311-323. · Zbl 1211.05044 |
| [57] | R. Lippert, R. Schwartz, G. Lancia, and S. Istrail, Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem, Briefings Bioinform., 3 (2002), pp. 23-31. |
| [58] | L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25 (1978), pp. 319-324. · Zbl 0418.05028 |
| [59] | L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25 (1979), pp. 1-7. · Zbl 0395.94021 |
| [60] | L. Lovász, An Algorithmic Theory of Numbers, Graphs, and Convexity, SIAM, Philadelphia, 1986. · Zbl 0606.68039 |
| [61] | E. Malaguti and P. Toth, An evolutionary approach for bandwidth multicoloring problems, European J. Oper. Res., 189 (2008), pp. 638-651. · Zbl 1146.90503 |
| [62] | M. Marek-Sadowska, An unconstrained topological via minimization problem for two-layer routing, IEEE Trans. Computer-Aided Design Integrated Circuits Systems, 3 (1984), pp. 184-190. |
| [63] | D. Marx, The complexity of tree multicolorings, in Mathematical Foundations of Computer Science, R. W. Diks K., ed., Lecture Notes in Comput. Sci., Springer, Berlin, 2002, pp. 532-542. · Zbl 1014.68117 |
| [64] | R. J. McEliece, E. R. Rodemich, and H. C. Rumsey, Jr., The Lovász bound and some generalizations, J. Combin. Inform. System Sci, 3 (1978), pp. 134-152. · Zbl 0408.05031 |
| [65] | A. Mehrotra and M. A. Trick, A branch-and-price approach for graph multi-coloring, in Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, E. K. Baker, A. Joseph, A. Mehrotra, and M. A. Trick, eds., Springer, Boston, 2007, pp. 15-29. · Zbl 1241.90185 |
| [66] | G. Narasimhan, The Maximum \(k-\) Colorable Subgraph Problem, Ph.D. thesis, University of Wisconsin-Madison, 1989. |
| [67] | G. Narasimhan and R. Manber, A Generalization of Lovász Sandwich Theorem, Tech. report, Department of Computer Sciences, University of Wisconsin-Madison, 1988. |
| [68] | L. Narayanan, Channel assignment and graph multicoloring, in Handbook of Wireless Networks and Mobile Computing, I. Stojmenović, ed., Wiley Online Library, 2002, pp. 71-94. |
| [69] | M. W. Newman, Independent Sets and Eigenspaces, Ph.D. thesis, University of Waterloo, 2004. |
| [70] | E. A. Nordhaus and J. W. Gaddum, On complementary graphs, Amer. Math. Monthly, 63 (1956), pp. 175-177. · Zbl 0070.18503 |
| [71] | W. Ogryczak and A. Tamir, Minimizing the sum of the \(k\) largest functions in linear time, Inform. Process. Lett., 85 (2003), pp. 117-122. · Zbl 1050.68155 |
| [72] | M. L. Overton and R. S. Womersley, Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices, Math. Program., 62 (1993), pp. 321-357. · Zbl 0806.90114 |
| [73] | G. Ren and Y. Bu, \(k\)-fold coloring of planar graphs, Sci. China Math., 53 (2010), pp. 2791-2800. · Zbl 1210.05049 |
| [74] | G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canad. J. Math., 9 (1957), pp. 515-525. · Zbl 0079.39202 |
| [75] | H. Sayama, Estimation of Laplacian spectra of direct and strong product graphs, Discrete Appl. Math., 205 (2016), pp. 160-170. · Zbl 1333.05188 |
| [76] | C. Shannon, The zero error capacity of a noisy channel, IRE Trans. Inform. Theory, 2 (1956), pp. 8-19. |
| [77] | Y. Shitov, Counterexamples to Hedetniemi’s conjecture, Ann. of Math., 190 (2019), pp. 663-667. · Zbl 1451.05087 |
| [78] | R. Singleton, Maximum distance \(q\)-nary codes, IEEE Trans. Inform. Theory, 10 (1964), pp. 116-118. · Zbl 0124.11505 |
| [79] | L. Sinjorgo, Multicoloring of Highly Symmetric Graphs, Master’s thesis, Tilburg University, The Netherlands, 2021. |
| [80] | S. Stahl, \(n\)-Tuple colorings and associated graphs, J. Combin. Theory Ser. B, 20 (1976), pp. 185-203. · Zbl 0293.05115 |
| [81] | A. P. Subramanian, H. Gupta, S. R. Das, and M. M. Buddhikot, Fast spectrum allocation in coordinated dynamic spectrum access based cellular networks, in Proceedings of the 2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks, 2007, pp. 320-330. |
| [82] | G. J. Tee, Eigenvectors of block circulant and alternating circulant matrices, New Zealand J. Math., 36 (2007), pp. 195-211. · Zbl 1186.15008 |
| [83] | V. G. Vizing, On an estimate of the chromatic class of a \(p\)-graph, Discret. Analiz., 3 (1964), pp. 25-30. · Zbl 1539.05042 |
| [84] | M. Yannakakis and F. Gavril, The maximum \(k\)-colorable subgraph problem for chordal graphs, Inform. Process. Lett., 24 (1987), pp. 133-137. · Zbl 0653.68070 |
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.
