Pith. sign in

REVIEW

Trisimplicial vertices in (fork, odd parachute)-free graphs

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2504.04496 v1 pith:ENRZGDY5 submitted 2025-04-06 math.CO

Trisimplicial vertices in (fork, odd parachute)-free graphs

classification math.CO
keywords graphtrisimplicialdivisibleomegaparachutevertexcontainsfork
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
Share X Bluesky LinkedIn Reddit HN
abstract

An {\em odd hole} in a graph is an induced subgraph which is a cycle of odd length at least five. An {\em odd parachute} is a graph obtained from an odd hole $H$ by adding a new edge $uv$ such that $x$ is adjacent to $u$ but not to $v$ for each $x\in V(H)$. A graph $G$ is perfectly divisible if for each induced subgraph $H$ of $G$, $V(H)$ can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $\omega(H[B])<\omega(H)$. A vertex of a graph is {\em trisimplicial} if its neighbourhood is the union of three cliques. In this paper, we prove that $\chi(G)\leq \binom{\omega(G)+1}{2}$ if $G$ is a (fork, odd parachute)-free graph by showing that $G$ contains a trisimplicial vertex when $G$ is nonperfectly divisible. This generalizes some results of Karthick, Kaufmann and Sivaraman [{\em Electron. J. Combin.} \textbf{29} (2022) \#P3.19], and Wu and Xu [{\em Discrete Math.} \textbf{347} (2024) 114121]. As a corollary, every nonperfectly divisible claw-free graph contains a trisimplicial vertex.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.