A Krausz partition of a graph G is a partition of the set of edges E(G), into complete subgraphs. A complete subgraph of G is called a cluster of G or a clique of G. Let v ? V (G) be a vertex of G. The number of clusters containing vertex v is said to order of v and maximum of these numbers is the order of partition. The Krausz dimension of the graph G is a minimal k such that G has Krausz partition of order k and is denoted by kdim(G). Notice that if G is disconnected, then the Krausz dimension is maximum Krausz dimension of all of component of G. Thus, without loss of generality we only consider connected graphs. In this dissertation, first we consider some computational complexity problems of Krause dimension of graphs. The decision problem of determining whether kdim(G) ? k and the problem of finding the Krausz dimension are denoted by KDIM(k) and KDIM, respectively. Among some results, we see that the determining of Krausz dimension of a Graph G, in general is NP-complete problem. Moreover, we explore computational complexity of Krausz dimension of some well-known families of graphs such as graphs with maximum degree at most four, graphs with bounded treewidth, interval graphs, chordal graphs, split graphs and complement of bipartite graphs. Then we study a generalization of Krausz dimension which is called m-Krausz dimension. Let m be an integer. A (k,m)-Krausz partition of G is a division of edges of G into the cliques such that each vertex belongs to at most k cliques and every two cliques have at most k vertices in common. Clearly if we set m = 1, then it is the Krausz dimension definition. Finally, in the last chapter, we explore the interpretation of Krausz dimension of graphs into the two other combinatorial concepts, namely set intersection representation of graphs and clique covering of graphs. A set representation for a graph G is a representation, in which we correspond a set to each vertex such that two vertices are adjacent if and only if theirs corresponding sets intersects. A clique covering for G is a collection of cliques such that each edge of G belongs to at least one of the cliques. If each vertex belongs to at most k cliques, it is called a k-clique cover. Minimum k for which there exists a k- clique cover for G is called local clique cover number of graph and is denoted by lcc(G). In fact, for a twin free graph G, lcc(G) = k means that there is a set intersection representation for G, in which each set is of size at most k.
