pith. sign in

arxiv: 1704.06667 · v1 · pith:YXJJJLC6new · submitted 2017-04-21 · 🧮 math.CO

Perfect divisibility and 2-divisibility

classification 🧮 math.CO
keywords omegadivisiblegraphdivisibilityfreeinducedpartitionedperfect
0
0 comments X
read the original abstract

A graph $G$ is said to be $2$-divisible if for all (nonempty) induced subgraphs $H$ of $G$, $V(H)$ can be partitioned into two sets $A,B$ such that $\omega(A) < \omega(H)$ and $\omega(B) < \omega(H)$. A graph $G$ is said to be perfectly divisible if for all induced subgraphs $H$ of $G$, $V(H)$ can be partitioned into two sets $A,B$ such that $H[A]$ is perfect and $\omega(B) < \omega(H)$. We prove that if a graph is $(P_5,C_5)$-free, then it is $2$-divisible. We also prove that if a graph is bull-free and either odd-hole-free or $P_5$-free, then it is perfectly divisible.

This paper has not been read by Pith yet.

discussion (0)

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