Coloring of some $(P_2\cup P_4)$-free graphs

Chen Ran; Zhang xiaowen

REVIEW 1 major objections 5 minor 20 references

Coloring of some $(P_2\cup P_4)$-free graphs

T0 review · 1 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that $(P_2\cup P_4)$-free diamond-free graphs satisfy $\chi(G)\le 2\omega(G)-1$ once $\omega(G)\ge 5$, with explicit small bounds for $\omega=2,3,4$, and that additionally forbidding $C_5$ makes the class perfect.

desk verdict New chi-binding bounds for subclasses of (P2∪P4)-free graphs; the case analyses mostly hold, but a definitional slip in the partition makes Claim 5.2 false as written and needs a one-line fix before the structural decomposition is sound. read the letter →

arxiv 2412.14524 v1 pith:J5U2L23J submitted 2024-12-19 math.CO

Chen Ran , Zhang xiaowen This is my paper · ORCID

classification math.CO MSC 05C1505C75

keywords (P2∪P4)-freegraphschromaticnumbercliqueperfectdiamond-freebindingfunctions

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes new upper bounds on the chromatic number of graphs that are $(P_2\cup P_4)$-free and also avoid one of three small graphs: a gem, a butterfly, or a diamond. For $(P_2\cup P_4)$-free graphs that are also gem-free it shows $\chi(G)\le 3\omega(G)-2$; for those that are butterfly-free it shows $\chi(G)\le (\omega(G)^2+3\omega(G)-2)/2$. The main case is $(P_2\cup P_4)$-free graphs that are diamond-free, where the paper proves $\chi(G)\le 4,7,9$ for $\omega(G)=2,3,4$ and $\chi(G)\le 2\omega(G)-1$ for $\omega(G)\ge 5$; the $\omega(G)=2$ bound is tight. It further proves that $(P_2\cup P_4)$-free, diamond-free, $C_5$-free graphs with $\omega(G)\ge 5$ are perfect. These are among the few explicit $\chi$-binding functions for a superclass of $(P_2\cup P_3)$-free graphs, and the diamond-free family is shown to behave linearly in the clique number once the clique is large.

What carries the argument

The central object is the partition of $V(G)$ relative to a maximum clique $A=\{v_1,\dots,v_{\omega(G)}\}$. For each pair $i<j$, $C_{i,j}$ collects vertices outside $A$ that are nonadjacent to both $v_i$ and $v_j$, assigned lexicographically, and $I_a$ collects vertices adjacent to every vertex of $A$ except $v_a$. In any $(P_2\cup P_4)$-free graph each $G[C_{i,j}]$ is $P_4$-free and therefore perfect, and each $I_a$ is a stable set; in diamond-free graphs only $C_{1,2},C_{1,3},C_{2,3}$ can be nonempty. The coloring arguments work by coloring these pieces separately and exploiting their proven adjacencies to $A$ and to each other.

What would settle it

A graph search that found a $(P_2\cup P_4)$-free, diamond-free, $C_5$-free graph with $\omega(G)\ge 5$ and an induced $C_7$ would refute Theorem 1.4; similarly, a $(P_2\cup P_4)$-free diamond-free graph with $\omega(G)=4$ and $\chi(G)=10$ would refute the $\omega=4$ case of Theorem 1.3.

Watch

Extended reading notes

Core claim

On its own terms, the central discovery is that forbidding a diamond alongside $P_2\cup P_4$ forces the vertex set of the graph to arrange itself around any maximum clique $A$ as $A\cup C_{1,2}\cup C_{1,3}\cup C_{2,3}$: every other piece of the partition from [2] and [18] is empty, and the surviving pieces have strong adjacency restrictions to $A$. That structure supports the piecewise bound $\chi(G)\le 4,7,9$ for $\omega(G)=2,3,4$ and $\chi(G)\le 2\omega(G)-1$ for $\omega(G)\ge 5$. The same partition, without the diamond restriction, gives $\chi(G)\le 3\omega(G)-2$ for gem-free graphs and $\chi(G)\le (\omega(G)^2+3\omega(G)-2)/2$ for butterfly-free graphs. When $C_5$ is also forbidden and $\omega(G)\ge 5$, the structure leaves $C_7$ as the only possible odd hole; a local argument rules out induced $C_7$'s, so the Strong Perfect Graph Theorem implies the graph is perfect.

Load-bearing premise

The proof of perfectness assumes, with only a one-word justification, that every odd hole of length at least 9 contains an induced $P_2\cup P_4$ and every odd antihole on at least 7 vertices contains a diamond; if either containment fails, the reduction to the Strong Perfect Graph Theorem collapses.

Editorial extensions

If this is right

For $(P_2\cup P_4)$-free diamond-free graphs, $\chi(G)\le 2\omega(G)-1$ whenever $\omega(G)\ge 5$, with the small-clique constants $4,7,9$ for $\omega(G)=2,3,4$.
The class of $(P_2\cup P_4)$-free diamond-free $C_5$-free graphs with $\omega(G)\ge 5$ is perfect, so every induced subgraph in this class satisfies $\chi(H)=\omega(H)$.
For $(P_2\cup P_4)$-free gem-free graphs, $\chi(G)\le 3\omega(G)-2$ holds for every clique number.
For $(P_2\cup P_4)$-free butterfly-free graphs, the quadratic bound $(\omega(G)^2+3\omega(G)-2)/2$ holds, and no linear binding function is possible for this class because it contains $2K_2$-free graphs, which already have no linear bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the $C_7$-exclusion argument is sound, then inside $(P_2\cup P_4)$-free diamond-free graphs with $\omega(G)\ge 5$, an induced $C_5$ is the only possible odd-hole obstruction to perfectness; describing those graphs would characterize all imperfect members of the class.
For other forbidden graphs that force most $C_{i,j}$ pieces of the partition to vanish, the same partition should yield comparable chromatic bounds, since the hard part of the proof is coloring $C_{1,2}$ and its adjacencies to $C_{1,3}\cup C_{2,3}$.
The paper gives no lower-bound examples for $\omega(G)\ge 3$, so whether $2\omega(G)-1$ is best possible remains open; constructing diamond-free $(P_2\cup P_4)$-free graphs requiring $2\omega(G)-1$ colors would settle that question.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Ran and Zhang prove new chi-binding functions for (P2∪P4)-free graphs with forbidden gem, butterfly, and diamond, plus a perfectness result for the diamond case with ω≥5. The bounds are genuinely new: earlier work on these subclasses was for (P2∪P3)-free graphs, and the general (P2∪P4) bound was cubic. The proofs extend the Wagon–Bharathi partition and the case analyses are competent. I checked the main arguments in Sections 3–5 and they are mostly coherent.

The paper has a load-bearing formal bug that needs fixing before publication. In Section 2, I_a is defined as {v ∈ V(G) : v∼x for all x∈A\{v_a} and v≁v_a}. Since A is a clique and the graph is simple, v_a itself satisfies both conditions, so I_a always contains v_a. Claim 5.2 then asserts I_a = ∅ for ω≥3, which is false; the proof only works for x outside A. The subsequent decomposition V = A ∪ C1,2 ∪ C1,3 ∪ C2,3 for ω≥3 relies on this claim. The fix is trivial—define I_a as a subset of V(G)\A—and the intended statement I_a \ A = ∅ is true, so the main theorems survive. But as written the proof is not formally sound.

There are a few smaller issues. In the proof of Theorem 1.1, the coloring counts G[M], G[N], and G[C1,2] but leaves v1 uncolored; you need to observe that v1 is anticomplete to C1,2 and can reuse one of its colors. That's an easy repair, but it's not stated. In Theorem 1.4, the reduction to the Strong Perfect Graph Theorem rests on two "clearly" facts: every odd hole of length ≥9 contains an induced P2∪P4, and every odd antihole with ≥7 vertices contains a diamond. Both are true but need a sentence of proof or a citation. Also, there are typos in the definition of N_{i3} in Section 5 Case 4 and in the abstract formula formatting.

None of this changes the central contribution: the new bounds are plausible and the case analyses seem to hold up. The paper deserves a serious referee—it's a solid extension in the chi-boundedness subfield, not a breakthrough, but the results are useful and the arguments are mostly rigorous. I'd recommend engaging with it and asking for a revision that fixes the I_a definition, adds the missing observation in Theorem 1.4, and corrects the small errors.

Referee Report

1 major / 5 minor

Summary. The paper studies chromatic bounds for (P2 ∪ P4)-free graphs with additional forbidden induced subgraphs. It proves four theorems: a linear bound χ(G) ≤ 3ω(G) − 2 for (P2 ∪ P4, gem)-free graphs (Theorem 1.1); a quadratic bound for (P2 ∪ P4, butterfly)-free graphs (Theorem 1.2); a case-based bound for (P2 ∪ P4, diamond)-free graphs, namely χ(G) ≤ 4, 7, 9, 2ω(G) − 1 according as ω(G) = 2, 3, 4, or ≥ 5 (Theorem 1.3); and perfectness of (P2 ∪ P4, diamond, C5)-free graphs with ω(G) ≥ 5 (Theorem 1.4). The proofs use a maximum-clique partition of the vertex set into sets Ci,j and Ia, the Strong Perfect Graph Theorem, and Seinsche's theorem on P4-free graphs.

Significance. If the results are correct, they form a useful contribution to the χ-binding literature for (P2 ∪ P4)-free graphs. The diamond-free case is the centerpiece: it gives a linear binding function for ω(G) ≥ 5 and a perfectness result for a natural subclass, going beyond the general polynomial bound for (P2 ∪ P4)-free graphs. The proofs are largely self-contained and the case analyses are checkable. The bound for ω(G) = 2 is tight via the Mycielski–Grötzsch graph, which is explicitly noted. The main weakness is a definitional slip in the partition that affects the formal validity of the structural claims; it is easily repaired, but it must be corrected before the paper is publishable.

major comments (1)

[Section 6, first paragraph] The reduction to the Strong Perfect Graph Theorem depends on two assertions stated as 'Clearly': that every odd hole of length at least 9 contains an induced P2 ∪ P4, and that every odd antihole with at least 7 vertices contains a diamond. These facts are true, but they are load-bearing: if either failed, the perfectness conclusion of Theorem 1.4 would not follow. The authors should supply a one- or two-sentence proof (or a citation) for both. The same paragraph also contains a typo: 'G is (C2k+1, C2k+1)-free' should read 'G is (odd hole, odd antihole)-free'.

minor comments (5)

[Section 5, Case 2 of Theorem 1.3] In the sentence about |Q′| = ω(G) − 1, the expression 'x ∈ N12 ∪ N12 ∪ N13' should read 'x ∈ N11 ∪ N12 ∪ N13'.
[Section 5, (M2)] The notation 'N1,3' should be 'N13' in the sentence 'Similarly, [N12, N1,3] = Ø'.
[Section 4] The displayed inequality for χ(G[C]) is typeset in a way that obscures the fraction; it should be χ(G[C]) ≤ ω(G) + (ω(G)2 − 1) = (ω(G)2 + ω(G) − 2)/2.
[References] In reference [10], the author name 'Karhick' should be 'Karthick'.
[Section 6, Claim 6.1] The phrase 'an K2 ∪ K1' should be 'a K2 ∪ K1'. Also, in the proof of Claim 6.1, several uses of 'by symmetry' would be easier to follow if the order of the induced P4 were fixed explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the chromatic bounds and perfectness results are derived from standard external theorems and explicit structural case analysis, not from their own conclusions.

full rationale

The paper's load-bearing claims (Theorems 1.1, 1.2, 1.3, and 1.4) are proved from first principles using the Wagon/Bharathi partition of V(G) into A, C_{i,j}, and I_a, together with two standard external results: the Strong Perfect Graph Theorem and Seinsche's theorem that every P4-free graph is perfect. The proofs then proceed by explicit case analysis and explicit colorings, and no parameter is fitted to the target bound and then renamed as a prediction. The only self-citation is reference [20] by coauthor Zhang, which appears in the introduction as motivational context for related (P2 ∪ P3)-free results and is never used in any proof, so it is not load-bearing. The 'Clearly' statements in Section 6 about odd holes of length at least 9 containing an induced P2 ∪ P4 and odd antiholes with at least 7 vertices containing a diamond are elementary graph observations, not assumptions equivalent to the graph being perfect. The claimed concern that the definition of I_a inadvertently includes the clique vertices of A makes Claim 5.2 literally false, since v_a ∈ I_a; however, this is a formal correctness defect in the written proof, not a circularity, because the intended statement I_a \ A = ∅ is sufficient for the decomposition V(G) = A ∪ C_{1,2} ∪ C_{1,3} ∪ C_{2,3} when ω(G) ≥ 3, and the paper's bounds do not depend on the false stronger statement. Thus the derivation chain is self-contained and no circular step is exhibited.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claims rest on standard external theorems and one elementary but unproved graph-theoretic observation. No free parameters or invented entities are introduced; the proofs are purely combinatorial.

assumptions (3)

standard math Strong Perfect Graph Theorem: a graph is perfect iff it is odd hole-free and odd antihole-free.
Used in Section 6 to conclude perfection from the absence of odd holes and odd antiholes after the C7-free reduction.
standard math Seinsche's theorem: every P4-free graph is perfect.
Invoked in Claim 2.1 to assert each G[C_{i,j}] is perfect, and in Section 3 for G[M] and G[N].
domain assumption Every odd hole of length at least 9 contains an induced P2∪P4, and every odd antihole with at least 7 vertices contains a diamond.
Stated without proof as 'Clearly' in the first paragraph of Section 6. It is true: in a long odd cycle, four consecutive vertices form a P4 anticomplete to a far edge; in an odd antihole, four suitably spaced vertices form a diamond. The proof should be included or cited.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Coloring of some $(P_2\cup P_4)$-free graphs." pith.science (2026). https://pith.science/paper/J5U2L23J

@misc{pith2026241214524,
  author       = {Pith},
  title        = {Pith review of: Coloring of some $(P_2\cup P_4)$-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J5U2L23J}},
  note         = {Machine review of arXiv:2412.14524}
}

abstract

We denote a path on $t$ vertices as $P_t$ and a cycle on $t$ vertices as $C_t$. For two vertex-disjoint graphs $G_1$ and $G_2$, the {\em union} $G_1\cup G_2$ is the graph with $V(G_1\cup G_2)=V(G_1)\cup V(G_2)$ and $E(G_1\cup G_2)=E(G_1)\cup E(G_2)$. A {\em diamond} (resp. {\em gem}) is a graph consisting of a $P_3$ (resp. $P_4$) and a new vertex adjacent to all vertices of the $P_3$ (resp. $P_4$), and a {\em butterfly} is a graph consisting of two triangles that share one vertex. In this paper, we show that $\chi(G)\le 3\omega(G)-2$ if $G$ is a ($P_2\cup P_4$, gem)-free graph, $\chi(G)\le \frac{\omega(G)^2+3\omega(G)-2}{2}$ if $G$ is a ($P_2\cup P_4$, butterfly)-free graph. We also study the class of ($P_2\cup P_4$, diamond)-free graphs, and show that, for such a graph $G$, $\chi(G)\leq4$ if $\omega(G)=2$, $\chi(G)\leq7$ if $\omega(G)=3$, $\chi(G)\leq9$ if $\omega(G)=4$, and $\chi(G)\leq2\omega(G)-1$ if $\omega(G)\ge 5$. Moreover, we prove that $G$ is perfect if $G$ is ($P_2\cup P_4$, diamond, $C_5$)-free with $\omega(G)\geq5$.

Figures

Figures reproduced from arXiv: 2412.14524 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 19 canonical work pages

[1]

J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, New York, 2008

2008
[2]

A. P. Bharathi and S. A. Choudum, Coloring of ( P3 ∪ P2)-free graphs, Graphs Comb., 34 (2018) 97-107

work page 2018
[3]

Brause, B

C. Brause, B. Randerath, I. Schiermeyer, E. Vumar, On the chromatic number of 2K2-free graphs, Disc. Appl. Math., 235 14-24 (2019)

work page 2019
[4]

Char, and T

A. Char, and T. Karthick, Optimal chromatic bound for ( P2 + P3, P2 + P3)-free graphs, J. Graph Theory, 105 (2024) 149-178

work page 2024
[5]

An optimal chromatic bound for ($P_2+P_3$, gem)-free graphs

A. Char, and T. Karthick, An optimal chromatic bound for ( P2 + P3, gem)-free graphs, arXiv:2405.17819, 2024. 12

work page Pith review arXiv 2024
[6]

Chudnovsky, N

M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas. The strong perfect graph theorem. Ann. of Math., 164 (2006) 51-229

work page 2006
[7]

Francis, A

P. Francis, A. Prashant, and S. F. Raj, Chromatic bounds for some subclasses of (P3∪P2)- free graphs, Algorith. Disc. Appl. Math., Lecture Notes in Computer Science, 13719 (2022) 15-21

work page 2022
[8]

Gy´ arf´ as, Problems from the world surrounding perfect graphs, Zastosowania Matem- atyki Applicationes Mathematicae, 19 (1987) 413-441

A. Gy´ arf´ as, Problems from the world surrounding perfect graphs, Zastosowania Matem- atyki Applicationes Mathematicae, 19 (1987) 413-441

work page 1987

Show all 20 references

[9]

Gy´ arf´ as, On Ramsey covering numbers, Coll

A. Gy´ arf´ as, On Ramsey covering numbers, Coll. Math. Soc. J´ anos Bolyai, 10 (1975) 801-816

1975
[10]

Karhick and S

T. Karhick and S. Mishra, On the chromatic number of (P6, diamond)-free graphs, Graphs Comb., 34 (2018) 677-692

2018
[11]

R. Li, J. Li and D. Wu, On the chromatic number of some ( P3 ∪ P2)-free graphs, arXiv:2308.15248, 2023

2023 arXiv
[12]

R. Li, J. Li and D. Wu, A tight linear chromatic bound for ( P3 ∪ P2, W4)-free graphs, arXiv:2308.08768, 2023

2023 arXiv
[13]

R. Li, D. Wu and J. Li, Optimal chromatic bound for ( P2 ∪ P3, house)-free graphs, arXiv:2308.05442, 2023

2023 arXiv
[14]

Prashant, S

A. Prashant, S. Francis Raj and M. Gokulnath, Linear χ-binding functions for ( P3 ∪ P2, gem)-free graphs, arXiv preprint arXiv:2305.11757, 2023

2023 arXiv
[15]

Schiermeyer, Chromatic number of P5-free graphs: Reed’s conjecture, Disc

I. Schiermeyer, Chromatic number of P5-free graphs: Reed’s conjecture, Disc. Math., 7 (2016) 1940-1943

2016
[16]

Seinsche, On a property of the class of n-colorable graphs, J

D. Seinsche, On a property of the class of n-colorable graphs, J. Comb. Theory Ser. B, 16 (1974) 191-193

1974
[17]

Sumner, Subtrees of a graph and the chromatic number, The theory and applications of graphs, John Wiley & Sons, New York, (1981), pp

D.P. Sumner, Subtrees of a graph and the chromatic number, The theory and applications of graphs, John Wiley & Sons, New York, (1981), pp. 557-576

1981
[18]

Wagon, A bound on the chromatic number of graphs without certain induced sub- graphs, J

S. Wagon, A bound on the chromatic number of graphs without certain induced sub- graphs, J. Comb. Theory Ser. B, 29 (1980) 345-346

1980
[19]

Wu, and B

D. Wu, and B. Xu, Coloring of some crown-free graphs, Graphs Comb., 39 (2023) 106

2023
[20]

Xu and X

B. Xu and X. Zhang, Structure and coloring of ( P3 ∪ P2)-free graphs. Sparse triangles, submitted for publication. 13

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [1]

J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, New York, 2008

2008

[2] [2]

A. P. Bharathi and S. A. Choudum, Coloring of ( P3 ∪ P2)-free graphs, Graphs Comb., 34 (2018) 97-107

work page 2018

[3] [3]

Brause, B

C. Brause, B. Randerath, I. Schiermeyer, E. Vumar, On the chromatic number of 2K2-free graphs, Disc. Appl. Math., 235 14-24 (2019)

work page 2019

[4] [4]

Char, and T

A. Char, and T. Karthick, Optimal chromatic bound for ( P2 + P3, P2 + P3)-free graphs, J. Graph Theory, 105 (2024) 149-178

work page 2024

[5] [5]

An optimal chromatic bound for ($P_2+P_3$, gem)-free graphs

A. Char, and T. Karthick, An optimal chromatic bound for ( P2 + P3, gem)-free graphs, arXiv:2405.17819, 2024. 12

work page Pith review arXiv 2024

[6] [6]

Chudnovsky, N

M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas. The strong perfect graph theorem. Ann. of Math., 164 (2006) 51-229

work page 2006

[7] [7]

Francis, A

P. Francis, A. Prashant, and S. F. Raj, Chromatic bounds for some subclasses of (P3∪P2)- free graphs, Algorith. Disc. Appl. Math., Lecture Notes in Computer Science, 13719 (2022) 15-21

work page 2022

[8] [8]

Gy´ arf´ as, Problems from the world surrounding perfect graphs, Zastosowania Matem- atyki Applicationes Mathematicae, 19 (1987) 413-441

A. Gy´ arf´ as, Problems from the world surrounding perfect graphs, Zastosowania Matem- atyki Applicationes Mathematicae, 19 (1987) 413-441

work page 1987