Let $G$ be a graph with chromatic number $\chi(G)$, clique number $\omega(G)$ and zero forcing number $Z(G)$. We establish new lower bounds on $Z(G)$ in terms of induced triangle-free subgraphs. In particular, we show that if a graph $G$ contains an induced triangle-free subgraph $H$ with minimum degree $\delta(H) \ge 3$, then $Z(G)\ge\delta(H)+1$. As consequences, we prove that every triangle-free graph satisfies $\chi(G)\le\max\{3,Z(G)\}$ and obtain an application to planar graphs. Moreover, we prove that $\chi(G)\le \frac{Z(G)}{2}+2$ for every triangle-free graph.
Let $P_t$ denote the induced path on $t$ vertices. Let $\omega(G)$ denote the maximum number of vertices in a clique of a graph $G$. Gy\'arf\'as (1987) proved that every $P_t$-free graph $G$ satisfies $\chi(G)\le(t-1)^{\omega(G)-1}$, and Gravier, Ho\`ang, and Maffray (2003) improved this to $\chi(G)\le (t-2)^{\omega(G)...
For a graph $G$, a proper edge coloring of $G$ is called a D-coloring if every diamond subgraph of $G$ is rainbow. Let $\chi'_D(G)$ be the D-chromatic index of $G$, which is the smallest integer $k$ such that $G$ admits a D-coloring with $k$ colors. Let $\Delta$ be the maximum degree of $G$. The only known Brooks-type...
The adjacent vertex distinguishing (AVD)-total chromatic number $\chi''_{a}(G)$ of a graph $G$ is the least integer $k$ for which $G$ has a proper total coloring $f$ with $k$ colors such that $C_G(u)\neq C_G(v)$ for every edge $uv\in E(G)$, where $C_G(u)=\{f(u)\}\cup\{f(uw):uw\in E(G)\}$. The AVD-total coloring conject...
A. Banerjee, J. Geetha, K. Somasundaram· 0 citations
A B-coloring of a graph $G$ is a proper edge-coloring in which every $4$-cycle receives four distinct colors; let $q_B(G)$ be the minimum number of colors in such a coloring. Every graph of maximum degree $\Delta$ is $K_{2,\Delta+1}$-free; hence the known $2\Delta$ bound for planar graphs with $\Delta\ge38$ (Kong et al...
For a graph $G$, let $L(G)=\max\{\omega(G),\lceil (|V(G)|+1)/(\alpha_{\min}(G)+1)\rceil\}$, where $\omega(G)$ is the clique number and $\alpha_{\min}(G)$ is the minimum, over all vertices $v$, of the largest size of an independent set containing $v$. Dybizba\'nski, Furma\'nczyk, and Mkrtchyan (Discrete Appl. Math. 354...
Juho Lauri· Discrete Applied Mathematics· 0 citations
Let $G$ be a graph. Under an \emph{injective edge coloring} of $G$, any two edges at distance $2$ or belonging to a common triangle receive distinct colors. The \emph{injective chromatic index} of $G$, denoted by $\chi'_{inj}(G)$, is the smallest integer $k$ such that $G$ admits an injective edge coloring with $k$ colo...
Lin Tian, Run-Ze Wang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
