REVIEW 2 major objections 4 minor 11 references
Well-hued graphs with first difference two
T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read For well-hued graphs with first difference two, the only connected example is a complete graph with one leaf per vertex.
desk verdict Proves the a2=a1+2 conjecture and adds useful characterizations; the key Lemma 5 has a gap as written, but it is a small fix, not a fatal flaw. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the neighborhood-intersection relation on a maximal independent set $I$: for $v\notin I$, $\Gamma(v,I)$ collects the vertices outside $I$ whose neighbors in $I$ are contained in $N_G(v)\cap I$, and $I_v$ is a maximum independent set inside $\Gamma(v,I)$. Lemma 1 forces $|N_G(v)\cap I| = |I_v|$ in every well-covered graph; for a well-hued graph with $a_2=a_1+2$, the excess $k=2$ then yields Lemmas 2 and 3, which force common neighbors in $I$ and force edges inside $V(G)-I$. Lemma 5, the load-bearing step, uses these constraints to rotate the independent set until every outside vertex sees exactly one vertex of $I$; from there the proof shows $V(G)-I$ is a clique and the pendant adjacencies are unique, producing precisely the corona of a complete graph.
What would settle it
Run an exhaustive search over all connected graphs of order up to 11, checking whether each is well-hued with $a_1\ge3$ and $a_2=a_1+2$; if any such graph is not the corona of a complete graph, Theorem 3 is false, while absence of a counterexample would support the characterization.
Extended reading notes
Core claim
The paper's central result is Theorem 3: if $G$ is a well-hued graph with $a_2=a_1+2$ and $a_1\ge3$, then $G$ is the corona of a complete graph. Equivalently, the vertex set splits into a clique $H$ and an independent set $I$, each vertex of $H$ is joined to exactly one vertex of $I$ as a pendant leaf, and no other edges exist, so $G\cong K_{a_1}\circ K_1$ and the sequence continues as $a_1,a_1+2,a_1+3,\dots,n$. This proves and strengthens the earlier conjecture, which had claimed the same for $a_1\ge4$. The proof works by taking a maximal independent set $I$ and studying, for each vertex $v$ outside it, the set $\Gamma(v,I)$ of outside vertices whose neighborhoods inside $I$ are contained in $N_G(v)\cap I$; a chain of lemmas reduces the excess $k=a_2-a_1=2$ to the statement that $I$ can be chosen so that every outside vertex has exactly one neighbor in $I$, after which the outside vertices must form a clique and the pendant structure follows.
Load-bearing premise
The classification rests entirely on the claim that, in any well-hued graph with $a_2=a_1+2$ and $a_1\ge3$, one can choose a maximal independent set (a largest set of vertices with no edges among them) such that every vertex outside it is adjacent to exactly one vertex of it; the proof of that claim is compressed and has an apparent set-membership typo, so if that claim fails the main characterization is unsupported.
Editorial extensions
If this is right
- For $a_1\ge3$, the first-difference-two case is closed: the only connected well-hued graph is $K_{a_1}\circ K_1$, so a sequence such as $(4,6,8,9,\dots)$ cannot belong to any connected well-hued graph.
- The $a_1=2$ case is nearly complete: sequences $(2,4,\dots,2k)$ are characterized by spanning subgraphs of $K_{2,\dots,2}$ with a $K_2$-free neighborhood condition, and the sequences $(2,4,\dots,2k,2k+1,\dots,n)$ are characterized when $n=2k+1$ or $n\ge3k$, leaving only $2k+1<n<3k$ open.
- For cographs, well-huedness is self-complementary: a cograph is well-equi-hued exactly when its complement is, and this can be read off from the cotree by the uniform assignment property.
- The join criterion from earlier work is sharpened: if a join of two graphs is well-hued, it is automatically well-equi-hued, and the union of two well-equi-hued cographs is well-equi-hued precisely when their clique numbers agree.
Reading between the lines
- The $\Gamma(v,I)$ neighborhood-intersection machinery is not tied to the number two; the same lemmas with $k=3$ should constrain the open $a_2=a_1+3$ case, and the known construction (a corona of a complete graph with an extra $K_2$ attached to a leaf) suggests what the extremal examples should look like.
- For $\alpha(G)=2$, the unresolved window $2k+1<n(G)<3k$ may be approachable by extending Theorem 6's description to allow more than one special vertex, with the alternating-dominating-set condition of Theorem 5 generalized to a small set of dominating vertices.
- The complement-closure result for cographs raises the paper's own closing question in sharper form: whether every connected well-hued graph whose complement is also well-hued must be built from joins and disjoint unions of well-equi-hued pieces, or whether the cograph examples in the paper's Figure 1 are special.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies well-hued graphs, i.e. graphs in which every maximal k-colorable subgraph has the same order a_k. Its main result (Theorems 2 and 3) is that every connected well-hued graph with a_2 = a_1 + 2 and a_1 >= 3 is the corona of a complete graph, settling a conjecture from Goddard, Kuenzel, and Melville. It then nearly characterizes connected well-hued graphs with a_1 = 2 (Theorems 4-6), and gives a cotree-based characterization of well-hued cographs (Theorems 9-11). The proof strategy is to develop lemmas about maximal independent sets in well-covered, well-bicovered graphs and then to force all vertices outside a carefully chosen independent set to have exactly one neighbor in that set.
Significance. If the main theorem is correct, it strengthens and settles Conjecture 1 of [6] (with a_1 >= 3 rather than a_1 >= 4) by a clean combinatorial argument. The a_1 = 2 results and the cograph characterization are useful additions, and the paper contains no fitted parameters and does not rely circularly on the conjecture itself; Theorem 1 from [6] is used mainly for context. However, the main theorem rests on Lemma 5, whose proof as written has a real gap (detailed below). The gap is repairable, but until repaired the central claim is not established.
major comments (2)
- [Section 2.2, Lemma 5] The sentence 'This same argument can be applied to all vertices x such that |N_G(x) cap I| = 2, implying that w'' is not adjacent to any vertex in (V(G)-I)-Gamma(w,I)' is a non sequitur as written. For a different vertex x', the common intersection produced by the same argument could in principle be a different vertex from w''. The proof must show that the intersection of I_w and I_{x'} is forced to be the original w'': since I_w = {w, w''} and w is not in Gamma(x',I) (because x' is outside Gamma(w,I) and therefore b is not in N_G(x') while b is in N_G(w)), the common vertex cannot be w. Then w'' lies in I_{x'}, and the independence of I_{x'} gives w''x' not in E(G). This argument is absent and is load-bearing for the construction of I'.
- [Section 2.2, Lemma 5] After defining I' = (I - {w'}) union {w''}, the proof does not verify that I' is a maximal independent set, although Corollary 4 (and the definition of well-hued) requires maximality. In particular, suppose v in Gamma(w,I) has N_G(v) cap I = {w'} and v w'' is not an edge. Then I' would not be maximal, since v could be added. This case must be ruled out, for example by observing that (I - {w'}) union {w'', v} would be an independent set of size a_1 + 1, contradicting alpha(G) = a_1. Without this verification, the application of Corollary 4 to I' is not justified.
minor comments (4)
- [Section 2.2, Lemma 5] The phrase 'x, w' in (V(G)-I)-Gamma(w,I)' contains a set-membership error: w' was defined as a vertex of I, so it cannot be an element of (V(G)-I)-Gamma(w,I). The intended statement should be rewritten to clarify which vertices are outside I' and which are outside Gamma(w,I).
- [Section 4.1, Corollary 7] The phrase 'well-equi-ued cographs' appears to be a typo for 'well-equi-hued cographs'.
- [Section 1] The sentence about 'a wide dirth of similar properties' should be corrected; likely 'a wide array' or 'a dearth' was intended, and reference [5] misspells 'Nowakowski' as 'Nowakoski'.
- [Section 3, Theorem 5] The proof of Theorem 5 is dense and would benefit from a short high-level explanation of how the alternating-path machinery corresponds to the recoloring argument in Theorem 4; this is not a correctness issue but would improve readability.
Circularity Check
No circularity: the main structural theorem is derived from the definitions and Lemmas 1-5, and the self-citations to [6] are prior independent results rather than assumed inputs.
full rationale
The derivation of Theorem 3 is self-contained. Lemmas 1-3 are proved directly from the well-covered and well-bicovered hypotheses; Lemma 4 applies them to the a2 = a1 + 2 case; Lemma 5 attempts to construct an independent set I with every outside vertex having exactly one neighbor in I; and Theorem 3 then argues that V(G) - I induces a clique and each I-vertex has one neighbor outside, yielding the corona. No step reuses its own conclusion: Lemma 5 does not assume the corona structure, and Theorem 3 does not invoke the statement it is proving. The only author-overlapping citations are to [6] (Goddard-Kuenzel-Melville), used for Theorem 1 (realizability of difference sequences), Corollary 2 (re-proved in this paper), Conjecture 1 (here proved, not assumed), and Theorem 7 (join characterization, used in Section 4). These are published, externally checkable results and are not fitted parameters; the main theorem does not depend on them. The proof gap in Lemma 5 noted by the skeptic - the inference that the common vertex w'' is nonadjacent to every vertex outside Gamma(w,I) - is a correctness or rigor concern, not circularity, because it does not consist in assuming the target graph is a corona. Accordingly, no circular step is present, and the appropriate score is 0 rather than a penalty for self-citation.
Assumptions & free parameters
assumptions (4)
- domain assumption Theorem 1 of [6]: a sequence {a_k} is realizable by a well-hued graph if and only if the difference sequence d_1 = a_1, d_k = a_k - a_{k-1} is non-increasing and eventually zero.
- domain assumption Theorem 7 of [6]: the join G = G1 v G2 is well-hued if and only if G1 and G2 are well-equi-hued and have equal independence number.
- domain assumption Cograph facts from [1]: cographs are exactly P4-free graphs, have cotree parse trees, and the cotree of the complement is obtained by swapping internal node labels.
- standard math Cographs are perfect graphs, so for a cograph G, the chromatic number equals the clique number.
Cite this review
Pith. "Pith review of Well-hued graphs with first difference two." pith.science (2026). https://pith.science/paper/4DK2CU2B
@misc{pith2026250604993,
author = {Pith},
title = {Pith review of: Well-hued graphs with first difference two},
year = {2026},
howpublished = {\url{https://pith.science/paper/4DK2CU2B}},
note = {Machine review of arXiv:2506.04993}
}
abstract
A graph $G$ is said to be well-hued if every maximal $k$-colorable subgraph of $G$ has the same order $a_k$. Therefore, if $G$ is well-hued, we can associate with $G$ a sequence $\{a_k\}$. Necessary and sufficient conditions were given as to when a sequence $\{a_k\}$ is realized by a well-hued graph. Further, it was conjectured there is only one connected well-hued graph with $a_2 = a_1 + 2$ for every $a_1 \ge 4$. In this paper, we prove this conjecture as well as characterize nearly all well-hued graphs with $a_1=2$. We also investigate when both $G$ and its complement are well-hued.
Figures
Reference graph
Works this paper leans on
-
[6]
W. Goddard, K. Kuenzel, and E. Melville, Well-hued graphs, Discrete Applied Math., 320: (2022) 370–380
work page 2022
-
[1]
D. G. Corneil, H. Lerchs, and L. Stewart Burlingham, Complement reducible graphs, Discrete Applied Math.,3(3): (1981) 163–174
work page 1981
-
[2]
A. S. Finbow and B. L. Hartnell, A game related to covering by stars, Ars Combin., 16: (1983) 189–198
work page 1983
-
[3]
A. S. Finbow, B. L. Hartnell, and R. J.Nowakowski, A characterization of well- covered graphs of girth 5 or greater, J. Combin. Theory Ser. B 57 (1993) 44–68
work page 1993
-
[4]
A. S. Finbow, B. L. Hartnell, and R. J. Nowakowski, A characterization of well- covered graphs that contain neither 4- nor 5-cycles, J. Graph Theory 18 (1994) 713–721
work page 1994
-
[5]
A. S. Finbow, B. L. Hartnell, and R. J. Nowakoski, Well-dominated graphs: a collection of well-covered ones, Ars Combin., 25-A: (1988) 5–10
work page 1988
-
[7]
W. Goddard, K. Kuenzel, and E. Melville, Graphs in which all maximal bipartite subgraphs have the same order, Aequationes Math., 94: (2020) 1241–1255
work page 2020
-
[8]
B. L. Hartnell, Well-covered graphs, J. Combin. Math. Combin. Comput., 29: (1999) 107–115
work page 1999
Show all 11 references
-
[9]
M. Lesk, M. D. Plummer, and W. R. Pulleyblank, Equi-matchable graphs, Graph theory and Combinatorics, Academic Press, London, 239-254 (1984)
1984
-
[10]
M. D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8: (1970) 91 – 98
1970
-
[11]
M. D. Plummer, Well-covered graphs: a survey, Quaestiones Math. 16 (1993) 253– 287. 23
1993
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.