Please use this identifier to cite or link to this item:
Title: Some properties and applications of odd-colorable r-hypergraphs
Authors: Yuan, X
Qi, L 
Shao, J
Ouyang, C 
Keywords: Chromatic number
Laplacian spectrum
Signless Laplacian spectrum
Issue Date: 2018
Publisher: Elsevier B.V.
Source: Discrete applied mathematics, 2018, v. 236, p. 446-452 How to cite?
Journal: Discrete applied mathematics 
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]→[r] such that for any edge {j1,j2,…,jr} of G, we have φ(j1)+φ(j2)+⋅⋯⋅+φ(jr)≡r∕2(modr). In this paper, we first determine that, if r=2q(2t+1) and n≥2q(2q−1)r, then the maximum chromatic number in the class of the odd-colorable r-hypergraphs on n vertices is 2q, which answers a question raised by V. Nikiforov recently in Nikiforov (2017). We also study some applications of the spectral symmetry of the odd-colorable r-hypergraphs given in the same paper by V. Nikiforov. We show that the Laplacian spectrum Spec(L(G)) and the signless Laplacian spectrum Spec(Q(G)) of an r-hypergraph G are equal if and only if r is even and G is odd-colorable. As an application of this result, we give an affirmative answer for the remaining unsolved case r⁄≡0(mod4) of a question raised in Shao et al. (2015) about whether Spec(L(G))=Spec(Q(G)) implies that L(G) and Q(G) have the same H-spectrum.
ISSN: 0166-218X
DOI: 10.1016/j.dam.2017.10.008
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.