For a graph $G$, $\chi(G)$ $(\omega(G))$ denote its chromatic (clique) number. A $P_5$ is the chordless path on five vertices, and a $4$-$wheel$ is the graph consisting of a chordless cycle on four vertices $C_4$ plus an additional vertex adjacent to all the vertices of the $C_4$. In this paper, we show that every ($P_5$, $4$-wheel)-free graph $G$ satisfies $\chi(G)\leq \frac{3}{2}\omega(G)$. Moreover, this bound is almost tight. That is, there is a class of ($P_5$, $4$-wheel)-free graphs $\cal L$ such that every graph $H\in \cal L$ satisfies $\chi(H)\geq\frac{10}{7}\omega(H)$. This generalizes/improves several previously known results in the literature.Comment: Revised compact version; Accepted for publication in Discrete Mathematic
A \emph{long unichord} in a graph is an edge that is the unique chord of some cycle of length at lea...
AbstractThe relation of chromatic aspects and the existence of certain induced subgraphs of a triang...
Given a set $\mathcal{H}$ of graphs, let $f_\mathcal{H}^\star\colon \mathbb{N}_{>0}\to \mathbb{N}_{>...
In this paper, we give an optimal $\chi$-binding function for the class of $(P_7,C_4,C_5)$-free grap...
Let $G$ be a graph. We use $\chi(G)$ and $\omega(G)$ to denote the chromatic number and clique numbe...
This article is made available open access through a Creative Commons Attribution 4.0 International ...
A graph G is H-free if it has no induced subgraph isomorphic to H. We prove that a $P_5$-free graph ...
For any positive integer $t$, a \emph{$t$-broom} is a graph obtained from $K_{1,t+1}$ by subdividing...
AbstractIt follows from the results of Karapetyan (1984), Gyárfás and Lehel (1985), and Kostochka (1...
For a number $l\geq 2$, let ${\cal{G}}_l$ denote the family of graphs which have girth $2l+1$ and ha...
A graph G is H-free if it has no induced subgraph isomorphic to H. We prove that a $P_5$-free graph ...
For a set of graphs H, we call a graph G H-free if G-S is non-isomorphic to H for each S⊆V(G) and ea...
AbstractFor G a collection of finite graphs, the bounded chromatic number χB(G) is the smallest numb...
AbstractWe give a complete structure description of (P5,gem)-free graphs. By the results of a relate...
AbstractIt is proved that if G is a triangle-free graph with v vertices whose independence number do...
A \emph{long unichord} in a graph is an edge that is the unique chord of some cycle of length at lea...
AbstractThe relation of chromatic aspects and the existence of certain induced subgraphs of a triang...
Given a set $\mathcal{H}$ of graphs, let $f_\mathcal{H}^\star\colon \mathbb{N}_{>0}\to \mathbb{N}_{>...
In this paper, we give an optimal $\chi$-binding function for the class of $(P_7,C_4,C_5)$-free grap...
Let $G$ be a graph. We use $\chi(G)$ and $\omega(G)$ to denote the chromatic number and clique numbe...
This article is made available open access through a Creative Commons Attribution 4.0 International ...
A graph G is H-free if it has no induced subgraph isomorphic to H. We prove that a $P_5$-free graph ...
For any positive integer $t$, a \emph{$t$-broom} is a graph obtained from $K_{1,t+1}$ by subdividing...
AbstractIt follows from the results of Karapetyan (1984), Gyárfás and Lehel (1985), and Kostochka (1...
For a number $l\geq 2$, let ${\cal{G}}_l$ denote the family of graphs which have girth $2l+1$ and ha...
A graph G is H-free if it has no induced subgraph isomorphic to H. We prove that a $P_5$-free graph ...
For a set of graphs H, we call a graph G H-free if G-S is non-isomorphic to H for each S⊆V(G) and ea...
AbstractFor G a collection of finite graphs, the bounded chromatic number χB(G) is the smallest numb...
AbstractWe give a complete structure description of (P5,gem)-free graphs. By the results of a relate...
AbstractIt is proved that if G is a triangle-free graph with v vertices whose independence number do...
A \emph{long unichord} in a graph is an edge that is the unique chord of some cycle of length at lea...
AbstractThe relation of chromatic aspects and the existence of certain induced subgraphs of a triang...
Given a set $\mathcal{H}$ of graphs, let $f_\mathcal{H}^\star\colon \mathbb{N}_{>0}\to \mathbb{N}_{>...