A Cvetković-type theorem for coloring of digraphs
type: Item
instance of: scholarly article
title: A Cvetković-type theorem for coloring of digraphs
zbMATH Open document ID: 1482.05137
author: Jaehoon Kim
author: Soyeon Kim
author: Suil O
author: Semin Oh
published in: Linear Algebra and its Applications
publication date: 2021-11-25T00:00:00Z
review text: A \(k\)-coloring of a digraph is a partition of the digraph into \(k\) sets. A \(k\)-coloring is said to be proper if each color class is acyclic. A digraph is \(k\)-colorable if it has a proper \(k\)-coloring. The chromatic number of a digraph is the minimum number \(k\) such that the digraph is \(k\)-colorable. It has been shown that if a graph is an \(n\)-vertex simple graph with the chromatic number \(k\), then its spectral radius is at most the spectral radius of the \(n\)-vertex balanced complete \(k\)-partite graph, yielding a certain bound. The question was whether or not this bound can be extended to digraphs. The purpose of this paper is to show that by analyzing the characteristic polynomial of a digraph, a tight upper bound for the spectral radius of the digraph can be found in terms of the number of vertices and the chromatic number of the digraph. It also characterizes when equality holds, thereby providing a simple proof of an early result.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C31
Mathematics Subject Classification ID: 15A18
zbMATH DE Number: 7433636
zbMATH Keywords: digraph
zbMATH Keywords: spectral radius
zbMATH Keywords: chromatic number
zbMATH Keywords: Cvetković theorem
Wikidata QID: Q113869471
MaRDI profile type: Publication
full work available at URL: j.laa.2021.10.022
OpenAlex ID: W3210429128
cites work: Q3215235
cites work: Q2716030
cites work: Eigenvalues and colorings of digraphs
cites work: The dichromatic number of a digraph
cites work: Spectral radius of digraphs with given dichromatic number
cites work: On the spectrum of an equitable quotient matrix and its application
cites work: The Eigenvalues of a Graph and Its Chromatic Number
DOI: 10.1016/J.LAA.2021.10.022
description: scientific article; zbMATH DE number 7433636