Pith. sign in

A tight linear chromatic bound for ($P_3\cup P_2, W_4$)-free graphs

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

For two vertex disjoint graphs $H$ and $F$, we use $H\cup F$ to denote the graph with vertex set $V(H)\cup V(F)$ and edge set $E(H)\cup E(F)$, and use $H+F$ to denote the graph with vertex set $V(H)\cup V(F)$ and edge set $E(H)\cup E(F)\cup\{xy\;|\; x\in V(H), y\in V(F)$$\}$. A $W_4$ is the graph $K_1+C_4$. In this paper, we prove that $\chi(G)\le 2\omega(G)$ if $G$ is a ($P_3\cup P_2, W_4$)-free graph. This bound is tight when $\omega =2$ and $3$, and improves the main result of Wang and Zhang. Also, this bound partially generalizes some results of Prashant {\em et al.}.

citation-role summary

background 1

citation-polarity summary

fields

math.CO 1

years

2024 1

verdicts

CONDITIONAL 1

roles

background 1

polarities

unclear 1

representative citing papers

Coloring of some $(P_2\cup P_4)$-free graphs

math.CO · 2024-12-19 · conditional · novelty 6.0

For (P2∪P4, gem)-free, (P2∪P4, butterfly)-free, and (P2∪P4, diamond)-free graphs, the paper establishes explicit χ-binding functions, and shows (P2∪P4, diamond, C5)-free graphs with clique number at least 5 are perfect.

citing papers explorer

Showing 1 of 1 citing paper.

  • Coloring of some $(P_2\cup P_4)$-free graphs math.CO · 2024-12-19 · conditional · none · ref 12 · internal anchor

    For (P2∪P4, gem)-free, (P2∪P4, butterfly)-free, and (P2∪P4, diamond)-free graphs, the paper establishes explicit χ-binding functions, and shows (P2∪P4, diamond, C5)-free graphs with clique number at least 5 are perfect.