A Study on Graph Operators and Colorings

Abstract

In 1972, Erdös - Faber - Lovász conjectured that, if H is a linear hypergraph consisting of n edges of cardinality n, then it is possible to color the vertices with n colors so that no two vertices with the same color are in the same edge. In this research work we give a method of coloring of the linear hypergraph H satisfying the hypothesis of the conjecture and we partially prove the Erdös - Faber - Lovász conjecture theoretically. Let G be a graph and KG be the set of all cliques of G, then the clique graph of G denoted by K(G) is the graph with vertex set KG and two elements Qi;Qj 2 KG form an edge if and only if Qi \Qj 6= /0. We prove a necessary and sufficient condition for a clique graph K(G) to be complete when G = G1 + G2, give a partial characterization for clique divergence of the join of graphs and prove that if G1, G2 are Clique-Helly graphs different from K1 and G = G1 G2, then K2(G) = G. Let G be a labeled graph of order a, finite or infinite, and let N(G) be the set of all labeled maximal forests of G. The forest graph of G, denoted by F(G), is the graph with vertex set N(G) in which two maximal forests F1, F2 of G form an edge if and only if they differ exactly by one edge, i.e., F2 = F1 −e+ f for some edges e 2 F1 and f 2= F1. Using the theory of cardinal numbers, Zorn’s lemma, transfinite induction, the axiom of choice and the well-ordering principle, we determine the F-convergence, Fdivergence, F-depth and F-stability of any graph G.