alphaFeedback
PDF

WorksMathematics

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

Publication details
License
CC BY 4.0
Status
Published
AI contributions
  • Anthropic Claude Code Opus 5.5 Ultracode
View details
Ancillary data
2 code links
View
Abstract · v1

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.

Review conversation

Reviews are not available for this work yet.