Coloring the normalized Laplacian for oriented hypergraphs

Aida Abiad; Raffaella Mulas; Dong Zhang

doi:10.1016/j.laa.2021.07.018

Coloring the normalized Laplacian for oriented hypergraphs

Aida Abiad
, Raffaella Mulas
, Dong Zhang

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

The independence number, coloring number and related parameters are investigated in the setting of oriented hypergraphs using the spectrum of the normalized Laplace operator. For the independence number, both an inertia–like bound and a ratio–like bound are shown. A Sandwich Theorem involving the clique number, the vector chromatic number and the coloring number is proved, as well as a lower bound for the vector chromatic number in terms of the smallest and the largest eigenvalue of the normalized Laplacian. In addition, spectral partition numbers are studied in relation to the coloring number.

Original language	English
Pages (from-to)	192-207
Number of pages	16
Journal	Linear Algebra and its Applications
Volume	629
Early online date	28 Jul 2021
DOIs	https://doi.org/10.1016/j.laa.2021.07.018
Publication status	Published - 15 Nov 2021
Externally published	Yes

Funding

The authors are grateful to the anonymous referee for the comments and suggestions that have greatly improved the first version of this paper. The research of A. Abiad is partially supported by the FWO grant 1285921N .

Funders	Funder number
Fonds Wetenschappelijk Onderzoek	1285921N

Access to Document

10.1016/j.laa.2021.07.018

Persistent URL (handle)

Persistent link

Cite this

@article{0ce677eac9354f779167600684809d42,

title = "Coloring the normalized Laplacian for oriented hypergraphs",

abstract = "The independence number, coloring number and related parameters are investigated in the setting of oriented hypergraphs using the spectrum of the normalized Laplace operator. For the independence number, both an inertia–like bound and a ratio–like bound are shown. A Sandwich Theorem involving the clique number, the vector chromatic number and the coloring number is proved, as well as a lower bound for the vector chromatic number in terms of the smallest and the largest eigenvalue of the normalized Laplacian. In addition, spectral partition numbers are studied in relation to the coloring number.",

author = "Aida Abiad and Raffaella Mulas and Dong Zhang",

year = "2021",

month = nov,

day = "15",

doi = "10.1016/j.laa.2021.07.018",

language = "English",

volume = "629",

pages = "192--207",

journal = "Linear Algebra and its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Coloring the normalized Laplacian for oriented hypergraphs

AU - Abiad, Aida

AU - Mulas, Raffaella

AU - Zhang, Dong

PY - 2021/11/15

Y1 - 2021/11/15

N2 - The independence number, coloring number and related parameters are investigated in the setting of oriented hypergraphs using the spectrum of the normalized Laplace operator. For the independence number, both an inertia–like bound and a ratio–like bound are shown. A Sandwich Theorem involving the clique number, the vector chromatic number and the coloring number is proved, as well as a lower bound for the vector chromatic number in terms of the smallest and the largest eigenvalue of the normalized Laplacian. In addition, spectral partition numbers are studied in relation to the coloring number.

AB - The independence number, coloring number and related parameters are investigated in the setting of oriented hypergraphs using the spectrum of the normalized Laplace operator. For the independence number, both an inertia–like bound and a ratio–like bound are shown. A Sandwich Theorem involving the clique number, the vector chromatic number and the coloring number is proved, as well as a lower bound for the vector chromatic number in terms of the smallest and the largest eigenvalue of the normalized Laplacian. In addition, spectral partition numbers are studied in relation to the coloring number.

UR - https://www.scopus.com/pages/publications/85111580438

UR - https://www.scopus.com/pages/publications/85111580438#tab=citedBy

U2 - 10.1016/j.laa.2021.07.018

DO - 10.1016/j.laa.2021.07.018

M3 - Article

SN - 0024-3795

VL - 629

SP - 192

EP - 207

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

ER -

Coloring the normalized Laplacian for oriented hypergraphs

Abstract

Funding

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this