Article in volume
Authors:
Title:
More tales of Hoffman: bounds for the vector chromatic number of a graph
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 159-169
Received: 2020-03-26 , Revised: 2020-08-02 , Accepted: 2020-08-03 , Available online: 2020-09-14 , https://doi.org/10.7151/dmgt.2358
Abstract:
Let $\chi(G)$ denote the chromatic number of a graph and $\chi_v(G)$ denote
the vector chromatic number. For all graphs $\chi_v(G) \le \chi(G)$ and for some
graphs $\chi_v(G) \ll \chi(G)$. Galtman proved that Hoffman's well-known lower
bound for $\chi(G)$ is in fact a lower bound for $\chi_v(G)$. We prove that two
more spectral lower bounds for $\chi(G)$ are also lower bounds for $\chi_v(G)$.
We then use one of these bounds to derive a new characterization of $\chi_v(G)$.
Keywords:
vector chromatic number, spectral bounds
References:
- 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 - R. Bhatia, Matrix Analysis (Springer, 1997).
https://doi.org/10.1007/978-1-4612-0653-8 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - A.J. Hoffman, On Eigenvalues and Colorings of Graphs, in: Graph Theory and its Applications, B. Harris, Ed. (Acad. Press, New York, 1970).
- 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 - 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 - 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 - 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 - C. Meyer, Matrix Analysis and Applied Linear Algebra (SIAM, 2000).
- V. Nikiforov, Chromatic number and spectral radius, Linear Algebra Appl. 426 (2007) 810–814.
https://doi.org/10.1016/j.laa.2007.06.005 - D.E. Roberson, Variations on a Theme: Graph Homomorphisms, PhD Thesis (University of Waterloo, 2013).
- 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 - 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 - X. Zhan, Matrix Inequalities, Lect. Notes Math. 1790 ( Springer, 2002).
https://doi.org/10.1007/b83956 - More Tales of Hoffman: bounds for the vector chromatic number of a graph,.
https://github.com/aneksteind/MoreTalesOfHoffman
Close