And obviously there will be no trivial vertex which has only 2 edges. I think triangle free graphs are (subjectively) easier than complicated graphs, i wonder if you know some heuristic approaches/steps specificly for triangle free graphs. Thanks in advance

  • $\begingroup$ Welcome to CS.SE! Have you done any research? e.g., searched with Google Scholar? It's helpful to know what you've already done, so we don't repeat things you've already tried. $\endgroup$ – D.W. Jun 29 '17 at 6:42
  • $\begingroup$ i haven't really searched specificly for triangle free graphs, i am now for about an hour. i am asking this question also as a starting point $\endgroup$ – xcvbnm Jun 29 '17 at 7:01
  • $\begingroup$ If you're willing to consider not just triangle-free, but all odd-cycle free graphs then you get a very nice class of graphs - bipartite graphs. You can have a look at the discussion here for how to find a maximum independent set in Bipartite graphs $\endgroup$ – Peeyush Kushwaha Jun 29 '17 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.