Geodesic
More tales of Hoffman: bounds for the vector chromatic number of a graph
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 159-169 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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: vector chromatic number, spectral bounds 
@article{DMGT_2023_43_1_a9,
     author = {Wocjan, Pawel and Elphick, Clive and Anekstein, David},
     title = {More tales of {Hoffman:} bounds for the vector chromatic number of a graph},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {159--169},
     year = {2023},
     volume = {43},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a9/}
}
TY  - JOUR
AU  - Wocjan, Pawel
AU  - Elphick, Clive
AU  - Anekstein, David
TI  - More tales of Hoffman: bounds for the vector chromatic number of a graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 159
EP  - 169
VL  - 43
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a9/
LA  - en
ID  - DMGT_2023_43_1_a9
ER  - 
%0 Journal Article
%A Wocjan, Pawel
%A Elphick, Clive
%A Anekstein, David
%T More tales of Hoffman: bounds for the vector chromatic number of a graph
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 159-169
%V 43
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a9/
%G en
%F DMGT_2023_43_1_a9
Wocjan, Pawel; Elphick, Clive; Anekstein, David. More tales of Hoffman: bounds for the vector chromatic number of a graph. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 159-169. http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a9/

[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. https://doi.org/10.1016/j.laa.2015.08.007

[2] R. Bhatia, Matrix Analysis (Springer, 1997). https://doi.org/10.1007/978-1-4612-0653-8

[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. https://doi.org/10.1016/j.jctb.2005.10.002

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

[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. https://doi.org/10.1016/j.jcta.2019.06.008

[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. https://doi.org/10.1137/S0097539703431391

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

[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. https://doi.org/10.1007/s00493-014-3132-1

[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. https://doi.org/10.1016/j.ejc.2019.04.001

[10] A.J. Hoffman, On Eigenvalues and Colorings of Graphs, in: Graph Theory and its Applications, B. Harris, Ed. (Acad. Press, New York, 1970).

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

[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). https://doi.org/10.1007/s10958-011-0392-9

[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. https://doi.org/10.1016/j.laa.2011.03.059

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

[15] C. Meyer, Matrix Analysis and Applied Linear Algebra (SIAM, 2000).

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

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

[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. https://doi.org/10.37236/2735

[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. https://doi.org/10.37236/8183

[20] X. Zhan, \textrm{Matrix Inequalities}, Lect. Notes Math. 1790 ( Springer, 2002). https://doi.org/10.1007/b83956

[21] More Tales of Hoffman: bounds for the vector chromatic number of a graph,. https://github.com/aneksteind/MoreTalesOfHoffman