Perfect Divisions in ( P 3 ∪ P 4, P 6,Bull)-Free Graphs

Hao Hu () and Bin Xiong ()
Additional contact information
Hao Hu: School of Mathematical Sciences, East China Normal University, Shanghai 200241, China
Bin Xiong: School of Mathematical Sciences, East China Normal University, Shanghai 200241, China

Mathematics, 2025, vol. 13, issue 21, 1-8

Abstract: A graph G is said to be perfect if ω ( H ) = χ ( H ) for every induced subgraph H of G , where ω ( H ) and χ ( H ) denote the clique number and the chromatic number of H . We say that a graph G admits a perfect division if its vertex set can be partitioned into two subsets A and B such that G [ A ] is perfect and ω ( G [ B ] ) < ω ( G ) . If every induced subgraph of G admits a perfect division, then G is called perfectly divisible . A graph P 3 ∪ P 4 is the disjoint union of paths P 3 and P 4 . A bull refers to the graph consisting of a triangle with two disjoint pendant edges. A homogeneous set X is a proper subset of V ( G ) with at least two vertices such that every vertex in V ( G ) ∖ X is either complete or anticomplete to X . In this paper, we prove that every ( P 3 ∪ P 4 , P 6 , bull)-free graph G with ω ( G ) ≥ 3 admits a perfect division, provided that G contains no homogeneous set. Moreover, we establish that this clique number condition is tight by presenting a counterexample with clique number of exactly 2.

Keywords: perfect divisibility; bull-free graphs; P 3 ∪ P 4 -free graphs; P 6 -free graphs; graph coloring (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/21/3358/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/21/3358/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:21:p:3358-:d:1776670

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().