【图论】关于一般图的几个问题

我们都知道，在二分图中，有以下结论：

这些结论在一般无向图中是否成立（蒟蒻自己认为是成立的，但不敢确定所以来问问）

如果 $1$ 的结论对一般图适用，那么我们求一般图的最大独立集大小是否可以转换为求其最大匹配（带花树）如果不适用，那当我没问这一条

我们都知道对于求一般图的最大独立集大小，可以转换为求补图的最大团大小，而这两个问题都是 NP 完全问题，只有暴力算法，比较常用的是 Bron-Kerbosch 算法，那么除此之外还有没有 OI 界常用的方法（蒟蒻百度看到的都是一群神仙玩意）

其实这才是根本问题：给定 $n$ 个点和 $m$ 个形如“如果选则了 $x$ 就不允许选则 $y$ ”的关系，求最多可以选则多少个点

这个问题除了做一般图的最大独立集以外还有没有办法？