Some properties and applications of odd-colorable r-hypergraphs

2016/06/16 by Xiying Yuan, Yuan, Xiying, Liqun Qi +5 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.1606.05045

openalex publication_date 2016/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let r≥2 and r be even. An r-hypergraph G on n vertices is called odd-colorable if there exists a map φ:[n]→\lbrack r] such that for any edge \j₁,j₂,⋯,j_r\ of G, we have φ(j₁)+φ(j₂)+⋅⋅⋅+φ(j_r)≡ r/2(modr). In this paper, we first determine that, if r=2^q(2t+1) and n≥ 2^q(2^q-1)r, then the maximum chromatic number in the class of the odd-colorable r-hypergraphs on n vertices is 2^q, which answers a question raised by V. Nikiforov recently in [V. Nikiforov, Hypergraphs and hypermatrices with symmetric spectrum. Prinprint available in arXiv:1605.00709v2, 10 May, 2016]. We also study some applications of the symmetric spectral property of the odd-colorable r-graphs given in that same paper by V. Nikiforov. We show that the Laplacian spectrum and the signless Laplacian spectrum of an r-hypergraph G are equal if and only if G is odd-colorable, and then study some further applications of these spectral properties.

Cited by

• Sharp lower bounds on the spectral radius of uniform hypergraphs concerning degrees

Related

• Some Spectral Properties and Characterizations of Connected Odd-bipartite Uniform Hypergraphs
• Hypergraphs and hypermatrices with symmetric spectrum
• Odd Ramsey numbers of multipartite graphs and hypergraphs
• Remarks on odd colorings of graphs
• New bounds for odd colourings of graphs