Pith. sign in

Optimal chromatic bound for ($P_3\cup P_2$, house)-free graphs

· 2023 · math.CO · arXiv 2308.05442

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

1 Pith paper citing it
open full Pith review browse 1 citing papers arXiv PDF
abstract

Let $G$ and $H$ be two vertex disjoint graphs. The {\em union} $G\cup H$ is the graph with $V(G\cup H)=V(G)\cup V(H)$ and $E(G\cup H)=E(G)\cup E(H)$. We use $P_k$ to denote a {\em path} on $k$ vertices, use {\em house} to denote the complement of $P_5$. In this paper, we show that $\chi(G)\le2\omega(G)$ if $G$ is ($P_3\cup P_2$, house)-free. Moreover, this bound is optimal when $\omega(G)\ge2$.

citation-role summary

background 1

citation-polarity summary

unclear 1

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 13 · 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.