# Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
## 7 Planar, Total, and Line Graphs  
In a graph, a vertex \(x\) and an edge \(e\) are _incident_ to each other if \(e\) connects \(x\) to another vertex. Two edges are _adjacent_ if they share a vertex in common. Let \(G\) and \(H\) be graphs such that each vertex \(x\in V(H)\) corresponds to an edge \(e_{x}\in E(G)\) and two vertices \(x,y\in V(H)\) are adjacent in \(H\) if and only if their corresponding edges \(e_{x}\) and \(e_{y}\) are adjacent in \(G\). Then, \(H\) is the _line graph_ of \(G\) and denoted by \(L(G)\). Let \(H^{\prime}\) be a graph such that \(V(H^{\prime})=V(G)\cup E(G)\) and two vertices \(x,y\in V(H^{\prime})\) are adjacent in \(H\) if and only if \(x\) and \(y\) are adjacent or incident to each other in \(G\). Then, \(H^{\prime}\) is the _total graph_ of \(G\) and denoted by \(T(G)\). Lemma 9 ([28]). : _The following statements hold for any triangle-free graph \(G\)._  
1. _Every maximal clique of_ \(L(G)\) _is the set of edges of_ \(G\) _incident to some vertex of_ \(G\)_._
2. _Two maximal cliques in_ \(L(G)\) _intersect if and only if their corresponding vertices (in_ \(G\)_) are adjacent in_ \(G\)_._  
Theorem 7.1.: _The MCIP is NP-complete for any 4-regular planar graph \(G\) with the clique number 3._  
Proof. : Since \(|C(G)|=O(n)\) for any planar graph \(G\)[29], the MCIP on planar graphs is in NP. Let \(\mathcal{G}\) be the class of triangle-free, 3-connected, cubic planar graphs. The independent set problem remains NP-complete even when restricted to the graph class \(\mathcal{G}\)[30]. We reduce this NP-complete problem to the MCIP for 4-regular planar graphs with the clique number 3 as follows. Let \(G\in\mathcal{G}\) and \(H=L(G)\). Clearly, we can construct \(H\) in polynomial time. By Lemma 9, we know that \(H\) is a 4-regular planar graph with \(\omega(H)=3\) and each maximal clique is a triangle in \(H\). Assume that \(D=\{x_{1},x_{2},\ldots,x_{\ell}\}\) is an independent set of \(G\) of maximum cardinality. Since \(G\in\mathcal{G}\), \(deg_{G}(x)=3\) for every \(x\in V(G)\). Let \(e_{i_{1}},e_{i_{2}},e_{i_{3}}\in E(G)\) have the vertex \(x_{i}\) in common for \(1\leq i\leq\ell\). Then, \(e_{i_{1}},e_{i_{2}},e_{i_{3}}\) form a triangle in \(H\). Let \(C_{i}\) be the triangle formed by \(e_{i_{1}},e_{i_{2}},e_{i_{3}}\) in \(H\) for \(1\leq i\leq\ell\). For each pair of vertices \(x_{j},x_{k}\in D\), \(x_{j}\) is not adjacent to \(x_{k}\) in \(G\). Therefore, \(C_{j}\) and \(C_{k}\) in \(H\) do not intersect. The set \(\{C_{1},C_{2},\ldots,C_{\ell}\}\) is an MCIS of \(H\). We have \(\alpha(G)\leq\alpha_{M}(H)\). Assume that \(S=\{C_{1},C_{2},\ldots,C_{\ell}\}\) is a maximum MCIS of \(H\). Then, each \(C_{i}\in S\) is a triangle in \(H\). Let \(C_{i}\) be formed by \(e_{i_{1}},e_{i_{2}},e_{i_{3}}\) in \(H\) for \(1\leq i\leq\ell\). Then, \(e_{i_{1}},e_{i_{2}},e_{i_{3}}\) are incident to the same vertex in \(G\). For \(1\leq i\leq\ell\), let \(e_{i_{1}},e_{i_{2}},e_{i_{3}}\in E(G)\) have the vertex \(x_{i}\) in common. For each pair of \(C_{j},C_{k}\in S\), \(C_{j}\) and \(C_{k}\) do not intersect. Therefore, \(x_{j}\) is not adjacent to \(x_{k}\) in \(G\). The set \(\{x_{1},x_{2},\ldots,x_{\ell}\}\) is an independent set of \(G\). We have \(\alpha_{M}(H)\leq\alpha(G)\). Hence, \(\alpha(G)=\alpha_{M}(H)\). For \(k\in\mathbb{N}\), we know that \(\alpha(G)\geq k\) if and only if \(\alpha_{M}(G)\geq k\). Corollary 5.: _The MCIP is NP-complete for line graphs of triangle-free, 3-connected, cubic planar graphs._  
Proof. : The corollary holds by the reduction of Theorem 7.1. Theorem 7.2.: _The MCIP problem is NP-complete for total graphs of triangle-free, 3-connected, cubic planar graphs._  
Proof. : Since \(|C(G)|=O(n)\) for a planar graph \(G\), the MCIP on planar graphs is in NP. Let \(\mathcal{G}\) be the classes of traingle-free, 3-connected, cubic planar graphs. The independent set problem remains NP-complete even when restricted to the graph class \(\mathcal{G}\)[30]. We reduce this NP-complete problem to MCIP for for total graphs of triangle-free, 3-connected, cubic planar graphs.