# Complexity consequence of logarithmic boolean width of co-bounded degree graphs?

The paper On graph classes with logarithmic boolean-width claims that the boolean width of co-k-degenerate graphs is at most $k\log{n}$ and a lot of graph vertex partition problems can be solved in polynomial time.

co-k-degenerate graphs include complements of bounded degree graphs. Clique is NP-hard on co-maximum degree 4.

On the other hand, graphclasses.org claims that clique is boolean width fixed parameter tractable, giving clique width as reference. Since $\exp{\log{n}}=n$ it could be polynomial.

Are there complexity consequence of logarithmic boolean width of co-bounded degree graphs? Like ETH not holding for them?

• Crossposted to MO: mathoverflow.net/questions/279158/… – joro Aug 21 '17 at 8:13
• FPT doesn't necessarily means that the dependence is exponential, thus it does not imply anything on ETH as long as you do not check the exact dependence. I may have time to check everything later this week, but from the top of my head, I think I remember that you may have an exponential blowup between cw and boolw, thus even if you have a single exponential dependency on the parameter for cw, it would not give much on boolw. – holf Aug 21 '17 at 10:00
• @holf Thanks. I think cliquewidth can be exponential in booleanwidth, but this need not answer the question. Some polynomial algorithms using only logarithmic booleanwidth are known, e.g. for dominating set. – joro Aug 21 '17 at 10:55
• Can you please remove one of these. Our site policy against simultaneously cross posting to several sites. (You can find the rational on help center.) – Kaveh Aug 21 '17 at 11:51