175
Views
1
CrossRef citations to date
0
Altmetric
Research Article

The high order spectrum of a graph and its applications in graph colouring and clique counting

, &
Pages 2354-2365 | Received 16 Oct 2021, Accepted 18 May 2022, Published online: 31 Jul 2022

References

  • Cvetković D, Doob M, Sachs H. Spectra of graphs. theory and applications. New York (NY): Academic Press; 1980.
  • Petersdorf M, Sachs H. Über spektrum, automorphismengruppe und Teiler eines graphen. (German) Wiss Z Tech Hochsch Ilmenau. 1969;15:123–128. Heft 4/5.
  • Nikiforov V. Analytic methods for uniform hypergraphs. Linear Algebra Appl. 2014;457:455–535.
  • Kang L, Nikiforov V, Yuan X. The p-spectral radius of k-partite and k-chromatic uniform hypergraphs. Linear Algebra Appl. 2015;478:81–107.
  • Qi L. Eigenvalues of a real supersymmetric tensor. J Symb Comput. 2005;40(6):1302–1324.
  • Lim L. Singular values and eigenvalues of tensors: a variational approach. IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. 2005;1:129–132.
  • Cooper J, Dutle A. Spectra of uniform hypergraphs. Linear Algebra Appl. 2012;436(9):3268–3292.
  • Hu S, Qi L. The Laplacian of a uniform hypergraph. J Comb Optim. 2015;29(2):331–366.
  • Zhou J, Sun L, Wang W, et al. Some spectral properties of uniform hypergraphs. Electron J Combin. 2014;21(P4):24.
  • Chen Y, Qi L, Zhang X. The Fiedler vector of a Laplacian tensor for hypergraph partitioning. SIAM J Sci Comput. 2017;39:2508–2537.
  • Fan Y, Huang T, Bao Y, et al. The spectral symmetry of weakly irreducible nonnegative tensors and connected hypergraphs. Trans Amer Math Soc. 2019;372(3):2213–2233.
  • Li H, Mohar B. On the first and second eigenvalue of finite and infinite uniform hypergraphs. Proc Amer Math Soc. 2019;147(3):933–946.
  • Clark J, Cooper J. A Harary-Sachs theorem for hypergraphs. J Combin Theory Ser B. 2021;149:1–15.
  • Friedland S, Gaubert S, Han L. Perron-Frobenius theorem for nonnegative multilinear forms and extensions. Linear Algebra Appl. 2013;438(2):738–749.
  • Bai S, Lu L. Spectral radius of {0,1}-tensor with prescribed number of ones. Linear Algebra Appl. 2018;558:205–235.
  • Yang Y, Yang Q. Further results for Perron-Frobenius theorem for nonegative tensors. SIAM J Matrix Anal Appl. 2010;31(5):2517–2530.
  • Morozov A, Shakirov S. Analogue of the identity log det = trace log for resultants. J Geom Phys. 2011;61(3):708–726.
  • Hu S, Huang Z, Ling C, et al. On determinants and eigenvalue theory of tensors. J Symb Comput. 2013;50:508–531.
  • Shao J, Qi L, Hu S. Some new trace formulas of tensors with applications in spectral hypergraph theory. Linear Multilinear Algebra. 2015;63(5):971–992.
  • Aigner M. A course in enumeration. Berlin Heidelberg: Springer; 2007.
  • Lick D, White A. k-degenerate graphs. Canad J Math. 1970;22(5):1082–1096.
  • Alon N, Kahn J, Seymour P. Large induced degenerate subgraphs. Graphs Combin. 1987;3(1):203–211.
  • Thomassen C. Decomposing a planar graph into degenerate graphs. J Combin Theory Ser B. 1995;65(2):305–314.
  • Abu-Khzam F, Feghali C, Heggernes P. Partitioning a graph into degenerate subgraphs. European J Combin. 2020;83: Article ID 103015.
  • Wilf H. The eigenvalues of a graph and its chromatic number. J London Math Sot. 1967;42:330–332.
  • Dirac G. Note on the colouring of graphs. Math Zeitschrift. 1951;54(4):347–353.
  • Brooks R. On coloring the nodes of a network. Proc Cambridge Phil Soc. 1941;37(2):194–197.
  • Bollobás B, Nikiforov V. Cliques and the spectral radius. J Combin Theory Ser B. 2007;97(5):859–865.
  • Cayley A. A theorem on trees. Quart J Pure Appl Math. 1889;23:376–378.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.