Chromatic Number and Dichromatic Polynomial of Digraphs

arXiv1711.06293MaRDI QIDQ6294072FDOQ6294072

Authors: Amir Hossein Ghodrati, Afrouz Jabalameli, Morteza Saghafian 

Publication date: 16 November 2017

Abstract: Let $G$ be a graph of order $n$. It is well-known that $alpha(G)geqsu{m}_{i=1}^{n}frac11+d_i$, where $alpha(G)$ is the independence number of $G$ and $d_1,ldots,d_n$ is the degree sequence of $G$. We extend this result to digraphs by showing that if $D$ is a digraph with $n$ vertices, then $alpha(D)geqsu{m}_{i=1}^{n}left(frac11+d_i^{+}+frac11+d_i^{-}-frac11+d_{i}ight)$, where $alpha(D)$ is the maximum size of an acyclic vertex set of $D$. Golowich proved that for any digraph $D$, $chi(D)leqlceilfrac4k5ceil+2$, where $k=max(Delt{a}^{+}(D),Delt{a}^{-}(D))$. We give a short and simple proof for this result. Next, we investigate the chromatic number of tournaments and determine the unique tournament such that for every integer $k>1$, the number of proper $k$-colorings of that tournament is maximum among all strongly connected tournaments with the same number of vertices. Also, we find the chromatic polynomial of the strongly connected tournament with the minimum number of cycles.

This page was built for publication: Chromatic Number and Dichromatic Polynomial of Digraphs

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