pith. sign in

arxiv: 1907.03913 · v1 · pith:Z3SBSLBXnew · submitted 2019-07-09 · 🧮 math.CO

Independent Sets in n-vertex k-chromatic, ell-connected graphs

John Engbers , Lauren Keough , Taylor Short This is my paper

Pith reviewed 2026-05-25 00:47 UTC · model grok-4.3

classification 🧮 math.CO
keywords independent setsk-chromatic graphsℓ-connected graphsextremal graph theorystabilityminimum degree
0
0 comments X

The pith

For large n a stability argument identifies the unique graph maximizing independent sets in k-chromatic ℓ-connected graphs.

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

The paper examines maximizing the number of independent sets in n-vertex graphs that are k-chromatic and ℓ-connected. For sufficiently large n a stability argument pins down a single extremal graph achieving the maximum total number of independent sets. The identical uniqueness result holds in the broader class of n-vertex k-chromatic graphs that only satisfy a minimum-degree condition of at least ℓ. Separate results treat maximization of independent sets of each fixed size inside 3-chromatic 2-connected graphs and the minimization of edges across all n-vertex k-chromatic ℓ-connected graphs.

Core claim

For n sufficiently large, a stability argument identifies the unique extremal n-vertex k-chromatic ℓ-connected graph that maximizes the total number of independent sets; the same graph is extremal in the larger family of n-vertex k-chromatic graphs with minimum degree at least ℓ.

What carries the argument

A stability argument that narrows candidate graphs until only one extremal example remains.

Load-bearing premise

The stability argument applies and yields a unique maximizer only when n is sufficiently large.

What would settle it

A k-chromatic ℓ-connected graph on some large n that contains strictly more independent sets than the claimed unique extremal graph.

Figures

Figures reproduced from arXiv: 1907.03913 by John Engbers, Lauren Keough, Taylor Short.

Figure 1
Figure 1. Figure 1: The graph G∗ for the two possibilities for k and ℓ. So, for example, when k = 2 ≤ ℓ we have G∗ = Kℓ,n−ℓ , and the fact that i(G) ≤ i(G∗ ) for all n-vertex ℓ-connected bipartite graphs G, with equality if and only if G = G∗ , appears as Corollary 2.2 in [1] (recall that an ℓ-connected graph has minimum degree at least ℓ). When ℓ = 1 and k > 1 the graph G∗ is formed from a k-clique with n − k pendants attach… view at source ↗
Figure 2
Figure 2. Figure 2: The construction for G∗ when ℓ < k − 1 and ℓ ≤ n − k. connected, there exists ℓ disjoint paths from the subset of vertices w1, w2, . . . , wℓ to the vertex w, and the same ℓ paths exists in H′ n−k,ℓ. Therefore in all cases there are ℓ disjoint paths between the vertices v and w. Since deleting the endpoints of the matching in Kk disconnects the graph, this shows that G∗ is ℓ-connected. Proof of Theorem 1.7… view at source ↗
Figure 3
Figure 3. Figure 3: The graph G∗ when ℓ − (n − k − 1) = 3; note that here w2 is adjacent to v2, v3, and v4. Next, we claim that G∗ is ℓ-connected; note that removing v1, . . . , vℓ disconnects the graph (as ℓ < k). We claim that any two vertices v and w are connected by ℓ disjoint paths. This is clear if 10 [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
read the original abstract

We study the problem of maximizing the number of independent sets in $n$-vertex $k$-chromatic $\ell$-connected graphs. First we consider maximizing the total number of independent sets in such graphs with $n$ sufficiently large, and for this problem we use a stability argument to find the unique extremal graph. We show that our result holds within the larger family of $n$-vertex $k$-chromatic graphs with minimum degree at least $\ell$, again for $n$ sufficiently large. We also maximize the number of independent sets of each fixed size in $n$-vertex 3-chromatic 2-connected graphs. We finally address maximizing the number of independent sets of size 2 (equivalently, minimizing the number of edges) over all $n$-vertex $k$-chromatic $\ell$-connected graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper investigates the maximum number of independent sets in n-vertex k-chromatic ℓ-connected graphs. For n sufficiently large, a stability argument is used to identify a unique extremal graph; the same graph is shown to be extremal in the broader family of n-vertex k-chromatic graphs with minimum degree at least ℓ. Additional results address the maximum number of independent sets of each fixed size in the 3-chromatic 2-connected case and the minimization of edges (equivalently, maximization of 2-vertex independent sets) over all such graphs.

Significance. If the stability reduction is valid, the result supplies a precise characterization of the extremal graph under chromatic-number and connectivity constraints, extending classical independent-set extremal problems. The extension to the minimum-degree family and the treatment of fixed-size independent sets are notable strengths. The stability approach itself is a standard and appropriate tool for this type of problem.

major comments (2)
  1. [Abstract and §1] Abstract and §1: the stability argument is asserted to produce a unique maximizer only for n sufficiently large, yet no explicit lower bound on n (in terms of k and ℓ) is supplied, nor is the magnitude of the stability error terms quantified. Without such a bound it is impossible to confirm that the identified graph is extremal in the stated regime or to exclude smaller-n counterexamples where the error terms dominate.
  2. [§3] §3 (stability reduction): the argument that the candidate graph is the unique maximizer relies on showing that any graph deviating from it has strictly fewer independent sets once n exceeds the (unspecified) threshold. The manuscript does not indicate how the connectivity condition ℓ is preserved or enforced in the stability step, leaving open whether the reduction applies uniformly to the ℓ-connected family.
minor comments (2)
  1. [§2] Notation for the extremal graph (presumably a complete k-partite graph with one large part and ℓ-1 additional vertices to enforce connectivity) should be introduced with a formal definition and diagram in §2.
  2. [§4] The proof that the result extends to minimum-degree-at-least-ℓ graphs is stated to follow the same stability argument; a short paragraph clarifying the (minor) adjustments needed would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation of the paper's significance and for the constructive major comments. We address each point below and indicate the revisions we will make.

read point-by-point responses

  1. Referee: [Abstract and §1] Abstract and §1: the stability argument is asserted to produce a unique maximizer only for n sufficiently large, yet no explicit lower bound on n (in terms of k and ℓ) is supplied, nor is the magnitude of the stability error terms quantified. Without such a bound it is impossible to confirm that the identified graph is extremal in the stated regime or to exclude smaller-n counterexamples where the error terms dominate.

    Authors: We agree that the manuscript does not supply an explicit lower bound on n. The stability analysis establishes that the difference in the number of independent sets between the candidate extremal graph and any deviating graph is negative once n is large enough for the leading terms to dominate the error terms (which depend on k and ℓ). An explicit n0(k,ℓ) can be derived in principle by tracking the constants through the inequalities, but doing so would require a lengthy expansion of the estimates without substantially strengthening the main result. We will revise the introduction and §3 to note that such a bound exists and can be obtained from the proof, while retaining the 'sufficiently large' phrasing as is standard for stability arguments. revision: partial

  2. Referee: [§3] §3 (stability reduction): the argument that the candidate graph is the unique maximizer relies on showing that any graph deviating from it has strictly fewer independent sets once n exceeds the (unspecified) threshold. The manuscript does not indicate how the connectivity condition ℓ is preserved or enforced in the stability step, leaving open whether the reduction applies uniformly to the ℓ-connected family.

    Authors: The stability reduction in §3 is performed entirely within the family of ℓ-connected k-chromatic graphs. The candidate graph is ℓ-connected, and the proof proceeds by contradiction: any graph in the family with more independent sets must be structurally close to the candidate. We will add an explicit paragraph in the revised §3 clarifying that the local modifications considered in the stability analysis (edge additions between non-adjacent vertices in different components of a cut and vertex identifications) are selected so that ℓ-connectivity is preserved whenever the original graph satisfies the condition. This ensures the reduction applies uniformly to the ℓ-connected family. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation is a direct stability proof

full rationale

The paper uses a stability argument to identify the unique maximizer of independent sets among n-vertex k-chromatic ℓ-connected graphs for sufficiently large n, and extends the result to the larger family with minimum degree at least ℓ. No quoted equations, definitions, or claims reduce a prediction or extremal graph to a fitted parameter, self-citation chain, or input by construction. The argument is presented as an independent combinatorial proof without self-definitional steps, ansatz smuggling, or renaming of known results. The unquantified threshold on n affects the result's effective range but does not create circularity in the derivation itself.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, invented entities, or non-standard axioms; the sole structural assumption is that n exceeds an unspecified threshold so that stability applies.

pith-pipeline@v0.9.0 · 5671 in / 1263 out tokens · 22993 ms · 2026-05-25T00:47:27.741638+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Alexander, J

    J. Alexander, J. Cutler, and T. Mink, Independent sets in graphs with given minimum degree, Electronic J. Combin. 19(3) (2012), #P37

    work page 2012

  2. [2]

    Bhasker, T

    J. Bhasker, T. Samad, and D. West, Size, chromatic number , and connectivity, Graphs Combin. 10 (1994), 209–213

    work page 1994

  3. [3]

    Cutler, Coloring graphs with graphs: a survey, Graph Theory Notes N.Y

    J. Cutler, Coloring graphs with graphs: a survey, Graph Theory Notes N.Y. 63 (2012), 7–16

    work page 2012

  4. [4]

    Dirac, The number of edges in critical graphs, J

    G.A. Dirac, The number of edges in critical graphs, J. Reine Angew. Math. 268/269 (1974) 150–164

    work page 1974

  5. [5]

    Engbers and A

    J. Engbers and A. Erey, Extremal colorings and independe nt sets, Graphs Combin. 34 (2018), 1347–1361

    work page 2018

  6. [6]

    Engbers and D

    J. Engbers and D. Galvin, Counting independent sets of a fi xed size in graphs with a given minimum degree, J. Graph Theory 76 (2014), 149–168

    work page 2014

  7. [7]

    J. Fox, X. He, and F. Manners, A proof of Tomescu’s graph co loring conjecture, J. Comb. Theory Ser. B 136 (2019), 204–221

    work page 2019

  8. [8]

    Gallai, Kritische Graphen I, Publ

    T. Gallai, Kritische Graphen I, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963), 165–192

    work page 1963

  9. [9]

    Gallai, Kritische Graphen II, Publ

    T. Gallai, Kritische Graphen II, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963), 373–395

    work page 1963

  10. [10]

    W. Gan, P. S. Loh, and B. Sudakov, Maximizing the number o f independent sets of a fixed size, Combin. Probab. Comput. 24(3) (2015), 521–527

    work page 2015

  11. [11]

    Harary, The Maximum Connectivity of a Graph, Proc

    F. Harary, The Maximum Connectivity of a Graph, Proc. Nat. Acad. Sci. USA 48 (1962), 1142–1146. 13

    work page 1962

  12. [12]

    Hua and S

    H. Hua and S. Zhang, Graphs with given number of cut verti ces and extremal Merrifield- Simmons index, Discrete Appl. Math. 159 (2011), 971–980

    work page 2011

  13. [13]

    A. V. Kostochka and M. Stiebitz, Colour-critical graph s with few edges, Discrete Math. 191 (1998), 125–137

    work page 1998

  14. [14]

    Krivelevich, An improved bound on the minimal number of edges in color-critical graphs, Electron J

    M. Krivelevich, An improved bound on the minimal number of edges in color-critical graphs, Electron J. Combin., 5 (1998) #R4

    work page 1998

  15. [15]

    Krivelevich, On the minimal number of edges in color- critical graphs, Combinatorica 17 (1997) 401–426

    M. Krivelevich, On the minimal number of edges in color- critical graphs, Combinatorica 17 (1997) 401–426

    work page 1997

  16. [16]

    Merrifield and H

    R. Merrifield and H. Simmons, Topological Methods in Chemistry , Wiley, New York, 1989

    work page 1989

  17. [17]

    Prodinger and R

    H. Prodinger and R. Tichy, Fibonacci numbers of graphs, Fibonacci Quart. 20 (1982), 16–21

    work page 1982

  18. [18]

    Zhao, Extremal regular graphs: independent sets and graph homomorphisms, Amer

    Y. Zhao, Extremal regular graphs: independent sets and graph homomorphisms, Amer. Math. Monthly 124 (2017), 827–843. 14

    work page 2017