Can I read Perfect Divisibility and 2-Divisibility on EtoBox?

Perfect Divisibility and 2-Divisibility by Chudnovsky, Maria; Sivaraman, Vaidy is a scholarly article available to read on EtoBox.

What is Perfect Divisibility and 2-Divisibility about?

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.

Author

Chudnovsky, Maria; Sivaraman, Vaidy

Published

2017

Language

EN