Perfect divisibility of some bull-free graphs and its application

Ran Chen, Paras Vinubhai Maniya, Di Wu, Junran Yu · 2026

Read Perfect divisibility of some bull-free graphs and its application by Ran Chen, Paras Vinubhai Maniya, Di Wu, Junran Yu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21538.txt.

Introduction

Chen and co-authors prove results about perfect divisibility in bull-free graphs. A bull is a small graph: a triangle with two disjoint pendant edges. A graph is perfectly divisible when every induced subgraph splits into a perfect part and a part with smaller clique number. Five open conjectures each claimed some graph class is perfectly divisible. The authors show all five hold when the graphs are also bull-free. They further prove that bull-free graphs avoiding a house, hammer, or diamond form perfect-Pollyanna classes.

Catalog record

CREATORRan Chen, Paras Vinubhai Maniya, Di Wu, Junran Yu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47658
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2603.21538

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Perfect divisibility of some bull-free graphs and its application Ran Chen, Paras Vinubhai Maniya, Di Wu, Junran Yu Abstract A graph G G is perfectly divisible if, for each induced subgraph H H of G G , V ⁡ ( H ) V(H) can be partitioned into A A and B B such that H ⁡ [ A ] H[A] is perfect and ω ⁡ ( H ⁡ [ B ] ) < ω ⁡ ( H ) \omega(H[B])<\omega(H) . A bull is a graph consisting of a triangle with two disjoint pendant edges. Hoàng [Discrete Math. 349 (2026) 114809] proposed four conjectures: 1. P 5 P_{5} -free graphs are perfectly divisible; 2. Odd hole-free graphs are perfectly divisible; 3. Even hole-free graphs are perfectly divisible; and 4. 4 ​ K 1 4K_{1} -free graphs are perfectly divisible. Karthick et al. [Electron. J. Combin. 29 (2022) P3.19] proposed a conjecture: Fork-free graphs are perfectly divisible. In this paper, we prove that all of five conjectures above hold for bull-free graphs. Our results also generalize some results of Chudnovsky and Sivaraman [J. Graph Theory 90 (2019) 54–60] and Karthick et al. [Electron. J. Combin. 29 (2022) P3.19]. We say that a class 𝒞 {\cal C} is perfect-Pollyanna if 𝒞 ∩ 𝒢 {\cal C}\cap{\cal G} is perfectly divisible for any hereditary class 𝒢 {\cal G} in which each triangle-free graph is 3-colorable. Let H ∈ { house, hammer, diamond } H\in\{\text{house, hammer, diamond}\} . In this paper, we prove that the class of ( bull , H ) (\text{bull},H) -free graphs is perfect-Pollyanna. Let 𝒞 {\cal C} be the class of ( bull , H ) (\text{bull},H) -free graphs. This implies that 𝒞 ∩ 𝒢 {\cal C}\cap{\cal G} is perfectly divisible if and only if all of triangle-free graphs in 𝒢 {\cal G} are perfectly divisible. As corollaries, we show that ( bull , ℋ ) (\text{bull},{\cal H}) -free graphs are perfectly divisible, where ℋ {\cal H} is one of { P 11 , C 4 } , { P 14 , C 5 , C 4 } \{P_{11},C_{4}\},\{P_{14},C_{5},C_{4}\} , and { P 17 , C 6 , C 5 , C 4 } \{P_{17},C_{6},C_{5},C_{4}\} . Key words and phrases: Perfectly divisibility; bull-free graphs; perfect-Pollyanna. AMS 2020 Subject Classifications: 05C15, 05C75 1 Introduction In this paper, we consider only finite and simple graphs. We follow [ 1 ] for basic graph-theoretic notation and terminology. Let P_{k} and C_{k} be a path and a cycle on k vertices respectively. We say that a graph G contains a graph H if H is isomorphic to an induced subgraph of G . A graph G is H - free if it does not contain H . Analogously, for a family \mathcal{H} of graphs, we say that G is \mathcal{H} -free if no member of \mathcal{H} is isomorphic to an induced subgraph of G . For a given positive integer k , we use [k] to denote the set \{1,\ldots,k\} . A k-coloring of a graph G=(V(G),E(G)) is a mapping f : V(G)\rightarrow[k] such that f(u)\neq f(v) whenever uv\in E(G) . We say that G is k-colorable if G admits a k -coloring. The chromatic number of G , denoted by \chi(G) , is the smallest positive integer k such that G is k -colorable. A clique (resp. stable set ) of G is a set of pairwise adjacent (resp. non-adjacent) vertices in G . The clique number of G , denoted by \omega(G) , is the maximum cardinality among all cliques of G . The concept of binding functions was introduced by Gyárfás [ 19 ] in 1975. A class of graphs is said to be hereditary if it is closed under isomorphism and induced subgraphs. For a hereditary class \mathcal{F} , if there exists a function f such that \chi(H)\leq f(\omega(H)) for every H\in\mathcal{F} , then \mathcal{F} is called \chi -bounded and f a binding function . An induced cycle of length k\geq 4 is called a hole , and k is the length of the hole. A k-hole is a hole of length k . A hole is odd if k is odd, and even otherwise. An antihole is the complement graph of a hole. A graph G is said to be perfect if \chi(H)=\omega(H) for every induced subgraph H of G . The Strong Perfect Graph Theorem [ 8 ] was established by Chudnovsky et al. in 2006. Theorem 1 ( [ 8 ] ) . A graph G is perfect if and only if G is ( odd hole, odd antihole ) -free. Figure 1: Illustration of some small graphs. A bull is a graph consisting of a triangle with two disjoint pendant edges. A house is the complement of P_{5} , a hammer is a graph obtained by identifying an end vertex of a P_{3} with a vertex of a triangle. A diamond is a graph consisting of two triangles sharing exactly one common edge. A fork is a graph obtained from K_{1,3} by subdividing an edge once. An E is a graph obtained from an induced P_{5}=v_{1}v_{2}v_{3}v_{4}v_{5} by adding an new vertex adjacent to only v_{3} in the P_{5} . An odd torch is a graph obtained from an odd hole by adding an edge such that one endpoint is not adjacent to any vertex of the odd hole, and the other endpoint is adjacent to the vertices of a stable set of the odd hole, for example, odd torch on a 5-hole is shown in Figure 1 . Let the vertices of V(G) be partitioned into two sets A and B . We say that (A,B) is a good partition of G if G[A] is perfect and \omega(G[B])<\omega(G) . A graph G is perfectly divisible if for every induced subgraph H contains a good partiton. This concept was proposed by Hoàng [ 16 ] . By a simple induction on \omega(G) , every perfectly divisible graph G satisfies \chi(G)\leq\binom{\omega(G)+1}{2} [ 11 ] . If G is non-perfectly divisible but every proper induced subgraph of G is perfectly divisible, then G is called minimally non-perfectly divisible , abbreviated as MNPD. Let G be a graph and let w be a weight function on V(G) . We use \omega_{w}(G) to denote the maximum weight of a clique in G . A graph G is perfectly weight divisible [ 11 , 16 ] if for every positive integer weight function w on V(G) , and for every induced subgraph H of G , there is a partition of V(H) into P and W such that H[P] is perfect and \omega_{w}(H[W])<\omega_{w}(H) . If G is non-perfectly weight divisible but every proper induced subgraph of G is perfectly weight divisible, then G is called minimally non-perfectly weight divisible , abbreviated as MNWD. It is certain that if a graph G is perfectly weight divisible, then G is perfectly divisible. We say that a class of graphs {\cal G} is perfectly weight divisible (resp. perfectly divisible) if every graph in {\cal G} is perfectly weight divisible (resp. perfectly divisible). Perfectly divisibility has been widely studied and discussed for a long time. Hoàng [ 16 ] proved that each (banner, odd hole)-free graph is perfectly

Read the complete text