Solutions to Edmonds' and Katona's problems on families of separating subsets

AbstractLet G be a finite loopless graph with vertex-set V(G) and edge-set E(G). Edmonds' problem is to determine the smallest integer, denoted by g(G), for which there exists a family A1, …, Ag(G) of subsets of V(G) such that for any adjacent xi,xj ϵ V(G) there are disjoint Ak and Al with xi ϵ Ak and xj ϵ Al.Katona's problem is the special case of Edmonds' problem when G is a complete graph.Let γ(G) denote the chromatic number of G. In this paper we establish g(G)=min{2p+3⌈log3(γ(G)/2p⌉ | p=0,1,2}, describe a simple method of constructing a required family for Katona's problem with minimal cardinality, and prove that the determination of g(G) is NP-complete