Perfect divisibility and 2-divisibility

Maria Chudnovsky, Vaidy Sivaraman

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

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 ω(A) < ω(H) and ω(B) < ω(H). (Here ω(G) denotes the clique number of G, the number of vertices in a largest clique of G). 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 ω(B) < ω(H). We prove that if a graph is (P5, C5) -free, then it is 2-divisible. We also prove that if a graph is bull-free and either odd-hole-free or P5-free, then it is perfectly divisible.

Original languageEnglish (US)
Pages (from-to)54-60
Number of pages7
JournalJournal of Graph Theory
Volume90
Issue number1
DOIs
StatePublished - Jan 2019

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • 2-divisibility
  • graph coloring
  • perfect divisibility

Fingerprint

Dive into the research topics of 'Perfect divisibility and 2-divisibility'. Together they form a unique fingerprint.

Cite this