A graph is balanced if it is bipartite and every induced cycle has length divisible by four. In his book, Gérard Cornuéjols proposed a number of open questions, offering $5000 for the solution of any of them. Here we solve three of them, about balanced graphs.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics