Planar graphs without 4- and 6-cycles are (7 : 2)-colorable (Q2185814)

Let \(s\), \(t\) be integers with \(s\le t\). Let \(G=(V,E)\) be a simple graph. A \((t:s)\)-coloring of \(G\) is a mapping \(\phi\) from \(V\) to \(s\)-subsets \(\{1,2,\dots,t\}\) such that \(\phi(u)\bigcap\phi(V)=\emptyset\) if \(uv\in E\). \(G\) is called \((t:s)\)-colorable if it has a \((t:s)\)-coloring. The authors prove that every planar graph without \(C_4\) and \(C_6\) is \((7:2)\)-colorable. This implies that every planar graph \(G\) without \(C_4\) and \(C_6\) has independence number at least \(\frac{2|V|}{7}\).