Proof Of Ding's Conjecture In Plane Graphs

X. Deng et al. proved Chvatal's conjecture on maximal stable sets and maximal cliques in graphs in 2004.Theorem 1 Let G be a graph with no induced subgraph isomorphic to F₃ or F₃. Then each maximal stable set meets each maximal clique in G if and only if each F₂ extends into an F₂^* in GG. Ding proposed the following conjecture as a generalization of Theorem 1.Conjecture Let G be a graph. Then each maximal stable set meets each maximal clique in G if and only if for every k ≥ 2, each F_k extends into an F_k^* in G and each F_k extends into an F_k^* in G.In this paper we prove that this conjecture is true for plane graphs and the complement of plane graphs, since a plane graph contains neither F₄^* nor F₄^*. The result we shall prove is : Theorem 2 Let Gbea plane graph or the complement of a plane graph. Then each maximal stable set meets each maximal clique in G if and only if each F_k extends into an F_k^* in G and each F_k extends into an F_k^* in G, for k — 2,3,4.Before proving Theorem 2 we do some research on the structure of graphs first. Then according to the configuration between S and C we finish the proof of Theorem 2.