A Cvetković-type theorem for coloring of digraphs

DOI10.1016/J.LAA.2021.10.022MaRDI QIDQ2052174zbMATH OpenOpenAlexWikidataFDO

Authors Jaehoon Kim, Soyeon Kim, Suil O, Semin Oh

Publication date 25 November 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/j.laa.2021.10.022

zbMATH Keywords

chromatic numberCvetković theoremdigraphspectral radius

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Graph polynomials (05C31) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

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.

Recommendations

• Colorings in digraphs from the spectral radius
• Spectral radius of digraphs with given dichromatic number
• Colorings and spectral radius of digraphs
• Chromatic number and spectral radius
• Spectral radii of graphs with given chromatic number

Cites work

• Eigenvalues and colorings of digraphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3425628 (Why is no real title available?)
• On the spectrum of an equitable quotient matrix and its application
• Spectral radius of digraphs with given dichromatic number
• The dichromatic number of a digraph
• The Eigenvalues of a Graph and Its Chromatic Number

Cited in

(8)

• An Erdős-Gallai type theorem for vertex colored graphs
• Colorings in digraphs from the spectral radius
• An extension of Richardson's theorem in m-colored digraphs
• Spectral radius of digraphs with given dichromatic number
• On a theorem of Cvetković in graph theory
• Sharp bounds for Laplacian spectral moments of digraphs with a fixed dichromatic number
• The A_ spectral moments of digraphs with a given dichromatic number
• Bounds for the eccentricity spectral radius of join digraphs with a fixed dichromatic number

This page was built for publication: A Cvetković-type theorem for coloring of digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2052174)