A hyper graph H is called linear if | E i ? E j | ?1 for all E i ,E j ? E(H), i j and is called k-uniform if all edges have the same cardinality k. The line graph L(H) of a hypergraph H=(V(H),E(H)) is a graph that , the vertices of L(H) are in a bijective corres pondence with the edge of H; and two vertices are adjacent in L(H) if and only if the corresponding edges have a nonempty intersection. The 2.25pt; HEIGHT: 18.75pt" id=_x0000_i1025 type="#_x0000_t75" respectively. let C={C 1 ,…,C q } be a clique covering of a graph G. We say C is linear if any two different cliques in C have no common edges and C is k-covering if every vertex of G belongs to at most k cliques from C . A linear k-covering is also called a Krausz k-covering (or Krausz k-partion, or Krausz k-decomposition). left; LINE-HEIGHT: normal; MARGIN: 0cm 0cm 0pt; unicode-bidi: embed; DIRECTION: ltr" The situation changes radically if one takes k ?3 instead of k=2. Lov ?sz posed the problem of characterizing the L 3 , and noted that it has no characterization by a finite list of forbidden induced subgraphs (a finite characterization) [36]. It has been showed that the recognition problem G L k l for k 3 is NP-complete. But the case k=3 is special, because in this and only in this situation the restrictions on vertex degrees are essential. This follows from the arguments below.
