1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

More Tales of Hoffman: Bounds for the Vector Chromatic Number of a Graph

Published Online: 29 Sep 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 26 Mar 2020
Accepted: 03 Aug 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Let χ(G) denote the chromatic number of a graph and χv(G) denote the vector chromatic number. For all graphs χv(G) ≤ χ(G) and for some graphs χv(G) ≪ χ(G). Galtman proved that Hoffman’s well-known lower bound for χ(G) is in fact a lower bound for χv(G). We prove that two more spectral lower bounds for χ(G) are also lower bounds for χv(G). We then use one of these bounds to derive a new characterization of χv(G).

Keywords

MSC 2010

[1] T. Ando and M. Lin, Proof of a conjectured lower bound on the chromatic number of a graph, Linear Algebra Appl. 485 (2015) 480–484. doi:10.1016/j.laa.2015.08.00710.1016/j.laa.2015.08.007Search in Google Scholar

[2] R. Bhatia, Matrix Analysis (Springer, 1997). doi:10.1007/978-1-4612-0653-810.1007/978-1-4612-0653-8Search in Google Scholar

[3] Y. Bilu, Tales of Hoffman: Three extensions of Hoffman’s bound on the chromatic number, J. Combin. Theory Ser. B 96 (2006) 608–613. doi:10.1016/j.jctb.2005.10.00210.1016/j.jctb.2005.10.002Search in Google Scholar

[4] C. Elphick and P. Wocjan, Unified spectral bounds on the chromatic number, Discuss. Math. Graph Theory 35 (2015) 773–780. doi:/10.7151/dmgt.183510.7151/dmgt.1835Search in Google Scholar

[5] C. Elphick and P. Wocjan, Spectral lower bounds on the quantum chromatic number of a graph, J. Combin. Theory Ser. A 168 (2019) 338–347. doi:10.1016/j.jcta.2019.06.00810.1016/j.jcta.2019.06.008Search in Google Scholar

[6] U. Feige, M. Langberg and G. Schechtman, Graphs with tiny vector chromatic number and huge chromatic numbers, SIAM J. Comput. 33 (2004) 1338–1368. doi:10.1137/S009753970343139110.1137/S0097539703431391Search in Google Scholar

[7] A. Galtman, Spectral characterizations of the Lovász number and the Delsarte number of a graph, J. Algebraic Combin. 12 (2000) 131–143. doi:10.1023/A:102658792611010.1023/A:1026587926110Search in Google Scholar

[8] C. Godsil, D.E. Roberson, R. Šamal and S. Severini, Sabidussi versus Hedetniemi for three variations of the chromatic number, Combinatorica 36 (2016) 395–415. doi:10.1007/s00493-014-3132-110.1007/s00493-014-3132-1Search in Google Scholar

[9] C. Godsil, D.E. Roberson, B. Rooney, R.Šamal and A. Varvitsiotis, Graph homomorphisms via vector colorings, European J. Combin. 79 (2016) 244–261. doi:10.1016/j.ejc.2019.04.00110.1016/j.ejc.2019.04.001Search in Google Scholar

[10] A.J. Hoffman, On eigenvalues and colorings of graphs, in: Graph Theory and its Applications, B. Harris, Ed. (Acad. Press, New York, 1970).10.1111/j.1749-6632.1970.tb45136.xSearch in Google Scholar

[11] D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming, J. ACM 45 (1998) 246–265. doi:10.1145/274787.27479110.1145/274787.274791Search in Google Scholar

[12] L. Yu. Kolotilina, Inequalities for the extreme eigenvalues of block-partitioned Hermitian matrices with applications to spectral graph theory, J. Math. Sci 176 (2011) 44–56 (translated from Zap. Nauchn. Sem. POMI 382 (2010) 82–103). doi:10.1007/s10958-011-0392-910.1007/s10958-011-0392-9Search in Google Scholar

[13] L.S. de Lima, C.S. Oliveira, N.M.M. de Abreu and V. Nikiforov, The smallest eigenvalue of the signless Laplacian, Linear Algebra Appl. 435 (2011) 2570–2584. doi:10.1016/j.laa.2011.03.05910.1016/j.laa.2011.03.059Search in Google Scholar

[14] L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979) 1–7. doi:10.1109/TIT.1979.105598510.1109/TIT.1979.1055985Search in Google Scholar

[15] C. Meyer, Matrix Analysis and Applied Linear Algebra (SIAM, 2000). doi:/10.1137/1.978089871951210.1137/1.9780898719512Search in Google Scholar

[16] V. Nikiforov, Chromatic number and spectral radius, Linear Algebra Appl. 426 (2007) 810–814. doi:10.1016/j.laa.2007.06.00510.1016/j.laa.2007.06.005Search in Google Scholar

[17] D.E. Roberson, Variations on a Theme: Graph Homomorphisms, PhD Thesis (University of Waterloo, 2013).Search in Google Scholar

[18] P. Wocjan and C. Elphick, New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix, Electron. J. Combin. 20 (2013) #P39. doi:10.37236/273510.37236/2735Search in Google Scholar

[19] P. Wocjan and C. Elphick, Spectral lower bounds for the orthogonal and projective ranks of a graph, Electron. J. Combin. 26 (2019) #P3.45. doi:10.37236/818310.37236/8183Search in Google Scholar

[20] X. Zhan, Matrix Inequalities, (Lect. Notes Math. 1790, Springer, 2002). doi:10.1007/b8395610.1007/b83956Search in Google Scholar

[21] https://github.com/aneksteind/MoreTalesOfHoffmanSearch in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo