Upper $k$-star-forming sets and $k$-independence in bipartite graphs
Sahbi conjectured that the $k$-independence number $\beta_k$ and the upper $k$-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\ge3$ we give a connected bipartite graph on $3k+3$ vertices with $\beta_k=2k+2$ and $\SF_k\ge3k$. On chain graphs, however, $\beta_k=\SF_k$ for every $k$. We also show, answering another of his questions, that deciding whether a bipartite graph has a minimal $2$-star-forming set with at least $t$ vertices is NP-complete.
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00498
curl -X POST /api/v1/records/hexagon/2610.00498/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00498/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'