Given a 3-uniform hypergraph H , its 2-intersection graph G has as vertex set the hyperedges of H and e e ′ is an edge of G whenever e and e ′ have exactly two common vertices in H . Di Marco et al. prove in Di Marco et al. (2023) that deciding whether a graph G is the 2-intersection graph of a 3-uniform hypergraph is N P -complete. Following this result, we study the class of claw-free graphs. We show that the recognition problem remains N P -complete for that class, but becomes polynomial if we consider triangulated claw-free graphs.

Abstract An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph G = (V,E) and a family $\cal {P}$ of chains Pi together with vectors h(Pi) = (h ,…,h ), one wants to find a partition V1,…,Vk of V such that for each Pi and each color j, |Vj ∩ Pi| = h . An interpretation in terms of scheduling is presented. We consider special cases of graphs and identify polynomially solvable cases; general complexity results are established in this case and also in the case where V1,…,Vk is required to be a proper vertex k‐coloring of G. Finally, we examine also the case of (proper) edge k‐colorings and determine its complexity status. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008