An independent set is a set of vertices in a graph, no two of which are adjacent. A maximum independent set is an independent set of largest possible size for a given graph $G$. This size is called the independence number of $G$ and is usually denoted by $\alpha(G)$.
Clearly, by Four Color Theorem a planar graph with $n$ vertices has $\alpha(G)\ge \lceil\frac{n}{4} \rceil$. My question is:
- Construct a class of $n$-vertex maximal planar graphs with chromatic number 4 and independence number $\lceil\frac{n}{4} \rceil + 1$
I found some some isolated examples; for example,
The first graph:
The second graph:
In the above figures, the set of vertices marked in red forms a maximum independent set (computed by a program; manual proof has not been considered yet).
g=Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}, {UndirectedEdge[1, 2], UndirectedEdge[1, 9], UndirectedEdge[1, 10], UndirectedEdge[1, 17], UndirectedEdge[2, 9], UndirectedEdge[2, 10], UndirectedEdge[2, 18], UndirectedEdge[3, 6], UndirectedEdge[3, 11], UndirectedEdge[3, 12], UndirectedEdge[3, 18], UndirectedEdge[4, 7], UndirectedEdge[4, 13], UndirectedEdge[4, 15], UndirectedEdge[4, 18], UndirectedEdge[5, 8], UndirectedEdge[5, 14], UndirectedEdge[5, 16], UndirectedEdge[5, 18], UndirectedEdge[6, 11], UndirectedEdge[6, 12], UndirectedEdge[6, 17], UndirectedEdge[7, 13], UndirectedEdge[7, 15], UndirectedEdge[7, 17], UndirectedEdge[8, 14], UndirectedEdge[8, 16], UndirectedEdge[8, 17], UndirectedEdge[9, 16], UndirectedEdge[9, 17], UndirectedEdge[9, 18], UndirectedEdge[10, 15], UndirectedEdge[10, 17], UndirectedEdge[10, 18], UndirectedEdge[11, 14], UndirectedEdge[11, 17], UndirectedEdge[11, 18], UndirectedEdge[12, 13], UndirectedEdge[12, 17], UndirectedEdge[12, 18], UndirectedEdge[13, 17], UndirectedEdge[13, 18], UndirectedEdge[14, 17], UndirectedEdge[14, 18], UndirectedEdge[15, 17], UndirectedEdge[15, 18], UndirectedEdge[16, 17], UndirectedEdge[16, 18]}, {FormatType -> TraditionalForm, VertexCoordinates -> {{0.8660254037844386, -0.5}, {0.6166100874945197, -0.30715269948566554}, {-0.2736640275958828, 0.01847285233728327}, {0.1662768775266119, -0.19630144780125747}, {-0.32562555182294917, 0.5519445010684977}, {-0.5681126648825919, -0.25172707364346164}, {-0.23902301144450533, -0.3591142237127319}, {-0.5888972745734184, 0.039257462028109924}, {-0.3117691453623983, 1.1477699788721916}, {0.5265434455009381, -0.39721934147924726}, {-0.46418961642845935, -0.005775858968680936}, {-0.1974537920628523, -0.07159378965629815}, {-0.020784609690826628, -0.07159378965629815}, {-0.31523324697753596, 0.3129214896239926}, {0.34641016151377513, -0.32793730917649216}, {-0.30484094213212265, 0.8810341545065845}, {-0.8660254037844386, -0.5}, {0.024248711305963955, 0.48612657038088036}}}]
S = FindIndependentVertexSet[g];
HighlightGraph[
Graph[g, VertexStyle -> Directive[Black], VertexSize -> Large,
EdgeStyle -> Directive[Thickness[0.008], Black]],
Style[S, {Red, AbsoluteThickness[10]}]]
I expect we can expand the found examples into a class using the following construction. Let $G$ be a $n$-vertex maximal plane graph with chromatic number $4$ and independence number $\lceil\frac{n}{4} \rceil + 1$. Let $G'$ be any maximal planar graph with $n'$ vertices and independence number $n'/4$. For instance, we can pick $G'=K_4$. Now pick any face $F$ of $G$ and draw into it $G'$. Now I expect we always can triangulate the part of $F$ which became "the outer face" of the drawing of $G'$, but I guess instead of the rigorous proof it is more easier and clear to deal with straight-line drawings. Then the obtained graph is a $n+n'$ maximal plane graph with chromatic number $4$ and independence number $\lceil\frac{n+n'}{4} \rceil + 1$.