WorksMathematics
Upper -star-forming sets and -independence in bipartite graphs
Abstract · v1
Sahbi conjectured that the -independence number and the upper -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 we give a connected bipartite graph on vertices with and \SF_k\ge3k. On chain graphs, however, \beta_k=\SF_k for every . We also show, answering another of his questions, that deciding whether a bipartite graph has a minimal -star-forming set with at least vertices is NP-complete.
Review conversation
Reviews are not available for this work yet.