For an integer k ≥ 2, a k-community structure in an undirected graph is a partition of its vertex set into k sets called communities, each of size at least two, such that every vertex of the graph has proportionally at least as many neighbours in its own community as in any other community. In this paper, we give a necessary and sufficient condition for a forest on n vertices to admit a k-community structure. Furthermore, we provide an O(k2 ・ n2)-time algorithm that computes such a k-community structure in a forest, if it exists. These results extend a result of Bazgan et al., 2018. We also show that if communities are allowed to have size one, then every forest with n ≥ k ≥ 2 vertices admits a k-community structure that can be found in time O(k2 ・ n2). We then consider threshold graphs and show that every connected threshold graph admits a 2-community structure if and only if it is not isomorphic to a star; also if such a 2-community structure exists, we explain how to obtain it in linear time. We further describe an infinite family of disconnected threshold graphs, containing exactly one isolated vertex, that do not admit any 2-community structure. Finally, we present a new infinite family of connected graphs that may contain an even or an odd number of vertices without 2-community structures, even if communities are allowed to have size one.

We continue the study initiated by Bonomo-Braberman and Gonzalez in 2020 on $r$-locally checkable problems. We propose a dynamic programming algorithm that takes as input a graph with an associated clique-width expression and solves a $1$-locally checkable problem under certain restrictions. We show that it runs in polynomial time in graphs of bounded clique-width, when the number of colors of the locally checkable problem is fixed. Furthermore, we present a first extension of our framework to global properties by taking into account the sizes of the color classes, and consequently enlarge the set of problems solvable in polynomial time with our approach in graphs of bounded clique-width. As examples, we apply this setting to show that, when parameterized by clique-width, the $[k]-$Roman domination problem is FPT, and the $k$-community problem, Max PDS and other variants are XP.

We consider the following problem of course scheduling and assignment of students. Students express their preferences for each course from several sets of proposed courses and each student has to take a certain number of courses from each set. A minimum number of students is required to open a course and a maximum number of students is specified for each course. The courses have to be scheduled on a limited number of periods so that simultaneous courses have no students in common. This problem can be seen as a generalization of the Student Project Allocation problem. It consists in determining which courses to open, specifying the schedule for these opened courses, and assigning students to them, so that their preferences are maximized. Our model is an Integer Programming problem, which we solve with a common available solver using an iterative process.