Pith. sign in

Linear $\chi$-binding functions for $\{P_3\cup P_2, gem\}$-free graphs

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

1 Pith paper citing it
abstract

Finding families that admit a linear $\chi$-binding function is a problem that has interested researchers for a long time. Recently, the question of finding linear subfamilies of $2K_2$-free graphs has garnered much attention. In this paper, we are interested in finding a linear subfamily of a specific superclass of $2K_2$-free graphs, namely $(P_3\cup P_2)$-free graphs. We show that the class of $\{P_3\cup P_2,gem\}$-free graphs admits $f=2\omega$ as a linear $\chi$-binding function. Furthermore, we give examples to show that the optimal $\chi$-binding function $f^*\geq \left\lceil\frac{5\omega(G)}{4}\right\rceil$ for the class of $\{P_3\cup P_2, gem\}$-free graphs and that the $\chi$-binding function $f=2\omega$ is tight when $\omega=2$ and $3$.

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