HEXAGONbeta

Upper kk-star-forming sets and kk-independence in bipartite graphs

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Deep Bhattacharjee ↗

Version 1 / Oct 23, 2026 / CC BY 4.0

Abstract

Sahbi conjectured that the kk-independence number βk\beta_k and the upper kk-star-forming number $\SF_k$ agree on bipartite graphs, and in particular on chain graphs, and asked whether $\beta_3=\SF_3$ on triangle-free graphs. For every k≥3k\ge3 we give a connected bipartite graph on 3k+33k+3 vertices with βk=2k+2\beta_k=2k+2 and $\SF_k\ge3k$. On chain graphs, however, $\beta_k=\SF_k$ for every kk. We also show, answering another of his questions, that deciding whether a bipartite graph has a minimal 22-star-forming set with at least tt vertices is NP-complete.

Provenance statement

Deep Bhattacharjee chose the problem and directed the work. Claude (Anthropic), through Claude Code, carried out the searches and computations, wrote the checking programs and the Lean 4 proofs and drafted the paper. Sahbi's Conjecture 4.1 false for k >= 3, Conjecture 6.4 true, Problem 9.3 NP-complete. The proofs are written out in the paper; the programs and their outputs are in the release. The author approved the final version. Code and data: release v1.1.0, https://github.com/creelie/Conjecture-002/releases/tag/v1.1.0.
AI provenance filesAI-PROVENANCE-HEXAGON.md · 1 KB

Tools used

Anthropic
Claude CodeVersion Opus 5.5 Ultracode

References

  1. AlyciaBHZ, Refute Sahbi Conjectures 4.1, 4.2 and 7.2 (arXiv:2610.03785): a 10-vertex bipartite graph with dissociation number 5 and a minimal 2-star-forming set of size 6 , pull request 14727 to the-omega-institute/trureturing, GitHub, 9 October 2026. https://github.com/the-omega-institute/trureturing/pull/14727arXiv
  2. D. Bhattacharjee, Upper kk-star-forming sets in bipartite graphs: paper, Lean 4 development and search programs , Zenodo, 2026. 10.5281/zenodo.23360032 ; https://github.com/creelie/Conjecture-002DOI
  3. M. Blidia, M. Chellali, O. Favaron and N. Meddah, On kk-independence in graphs with emphasis on trees , Discrete Math. 307 (2007), 2209--2216. 10.1016/j.disc.2006.11.007DOI
  4. M. Chellali and O. Favaron, On kk-star-forming sets in graphs , J. Combin. Math. Combin. Comput. 68 (2009), 205--214. Zbl 1176.05052.
  5. M. Chellali, O. Favaron, A. Hansberg and L. Volkmann, kk-domination and kk-independence in graphs: a survey , Graphs Combin. 28 (2012), 1--55. 10.1007/s00373-011-1040-3DOI
  6. E. J. Cockayne, O. Favaron, C. Payan and A. G. Thomason, Contributions to the theory of domination, independence and irredundance in graphs , Discrete Math. 33 (1981), 249--258. 10.1016/0012-365X(81)90268-5DOI
  7. J. F. Fink and M. S. Jacobson, nn-domination in graphs , in: Graph Theory with Applications to Algorithms and Computer Science (Kalamazoo, 1984), Wiley, New York, 1985, 283--300. Zbl 0573.05049.
  8. M. R. Garey, D. S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems , Theoret. Comput. Sci. 1 (1976), 237--267. 10.1016/0304-3975(76)90059-1DOI
  9. R. M. Karp, Reducibility among combinatorial problems , in: Complexity of Computer Computations, Plenum, New York, 1972, 85--103. 10.1007/978-1-4684-2001-2_9DOI
  10. The mathlib Community, The Lean mathematical library , in: Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), ACM, New York, 2020, 367--381. 10.1145/3372885.3373824DOI
Show all 14 referencesShow fewer references
  1. B. D. McKay and A. Piperno, Practical graph isomorphism, II , J. Symbolic Comput. 60 (2014), 94--112. 10.1016/j.jsc.2013.09.003DOI
  2. L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci. 12699 , Springer, Cham, 2021, 625--635. 10.1007/978-3-030-79876-5_37DOI
  3. R. Sahbi, Upper kk-star-forming sets, kk-independence, and upper domination , preprint, arXiv:2610.03785v2 (https://arxiv.org/abs/2610.03785v2), 6 October 2026; withdrawn by the author on 12 October 2026.arXiv
  4. M. Yannakakis, Node-deletion problems on bipartite graphs , SIAM J. Comput. 10 (1981), 310--327. 10.1137/0210022DOI

Version history

  1. v1Submitted by Deep BhattacharjeeInitial depositCurrentOct 23, 2026