On Characterizations of Trees Having Large $(2,0)$-Chromatic Numbers

Abstract

For a nontrivial connected graph $G$, let $c:V(G)\to {\mathbb{Z}}_2$ be a vertex coloring of $G$ where $c(v)\ne 0$ for at least one vertex $v$ of $G$. Then the coloring $c$ induces a new coloring $\sigma :V(G)\to {\mathbb{Z}}_2$ defined by $\sigma (v)=\sum _{u\in N[v]}c(u)$, where $N[v]$ is the closed neighborhood of $v$ and addition is performed in ${\mathbb{Z}}_2$. If $\sigma (v)=0\in {\mathbb{Z}}_2$ for every vertex $v$ in $G$, then the coloring $c$ is called a modular monochromatic $(2,0)$-coloring of $G$. A graph $G$ having a modular monochromatic $(2,0)$-coloring is a monochromatic $(2,0)$-colorable graph. The minimum number of vertices colored 1 in a modular monochromatic $(2,0)$-coloring of $G$ is the $(2,0)$-chromatic number ${\chi }_{(2,0)}(G)$ of $G$. A monochromatic $(2,0)$-colorable graph $G$ of order $n$ is $(2,0)$-extremal if ${\chi }_{(2,0)}(G)=n$. It is known that a tree $T$ is $(2,0)$-extremal if and only if every vertex of $T$ has odd degree. In this work, we characterize all trees of order $n$ having $(2,0)$-chromatic number $n-1$, $n-2$, or $n-3$, and investigate the structures of connected graphs having large $(2,0)$-chromatic numbers.