Search

For two integers r, l ≥ 0, a graph G = (V, E) is an (r, l)-graph if V can be partitioned into r independent sets and l cliques. In the parameterized (r, l)-Vertex Deletion problem, given a graph G and an integer k, one has to decide whether at most k vertices can be removed from G to obtain an (r, l)-graph. This problem is NP-hard if r + l ≥ 1 and encompasses several relevant problems such as Vertex Cover and Odd Cycle Transversal. The parameterized complexity of (r, l)-Vertex Deletion was known for all values of (r, l) except for (2,1), (1,2), and (2,2). We prove that each of these three cases is FPT and, furthermore, solvable in single-exponential time, which is asymptotically optimal in terms of k. We consider as well the version of (r, l)-Vertex Deletion where the set of vertices to be removed has to induce an independent set, and provide also a parameterized complexity dichotomy for this problem.

Let \({\mathcal P}\) be a partial order and \({\mathcal A}\) an arboreal extension of it (i.e. the Hasse diagram of \({\mathcal A}\) is a rooted tree with a unique minimal element). A jump of \({\mathcal A}\) is a relation contained in the Hasse diagram of \({\mathcal A}\), but not in the order \({\mathcal P}\). The arboreal jump number of \({\mathcal A}\) is the number of jumps contained in it. We study the problem of finding the arboreal extension of \({\mathcal P}\) having minimum arboreal jump number—a problem related to the well-known (linear) jump number problem. We describe several results for this problem, including NP-completeness, polynomial time solvable cases and bounds. We also discuss the concept of a minimal arboreal extension, namely an arboreal extension whose removal of one jump makes it no longer arboreal.

A graph G is called well covered if every two maximal independent sets of G have the same number of vertices. In this paper we shall use the modular and primeval decomposition techniques to decide well coveredness of graphs such that, either all their P 4-connected components (in short, P 4-components) are separable or they belong to well known classes of graphs that, in some local sense, contain few P 4's. In particular, we shall consider the class of cographs, P 4-reducible, P 4-sparse, extended P 4-reducible, extended P 4-sparse graphs, P 4-extendible graphs, P 4-lite graphs, and P 4-tidy graphs.

Let G=(V,E) be a graph with n vertices. A clique-colouring of a graph is a colouring of its vertices such that no maximal clique of size at least two is monocoloured. A k-clique-colouring is a clique-colouring that uses k colours. The clique-chromatic number of a graph G is the minimum k such that G has a k-clique-colouring. In this paper we will use the primeval decomposition technique to find the clique-chromatic number and the clique-colouring of well known classes of graphs that in some local sense contain few P 4’s. In particular we shall consider the classes of extended P 4-laden graphs, p-trees (graphs which contain exactly n−3 P 4’s) and (q,q−3)-graphs, q≥7, such that no set of at most q vertices induces more that q−3 distincts P 4’s. As corollary we shall derive the clique-chromatic number and the clique-colouring of the classes of cographs, P 4-reducible graphs, P 4-sparse graphs, extended P 4-reducible graphs, extended P 4-sparse graphs, P 4-extendible graphs, P 4-lite graphs, P 4-tidy graphs and P 4-laden graphs that are included in the class of extended P 4-laden graphs.

International audience; The chain graph sandwich problem asks: Given a vertex set $V$, a mandatory edge set $E^1$, and a larger edge set $E^2$, is there a graph $G= (V,E)$ such that $E^1 \subseteq E \subseteq E^2 $ with $G$ being a chain graph (i.e., a $2K_2$-free bipartite graph)? We prove that the chain graph sandwich problem is NP-complete. This result stands in contrast to (1) the case where $E^1$ is a connected graph, which has a linear-time solution, (2) the threshold graph sandwich problem, which has a linear-time solution, and (3) the chain probe graph problem, which has a polynomial-time solution.

In Hell et al. (2004), we have previously observed that, in a chordal graph G, the maximum number of independent r -cliques (i.e., of vertex disjoint subgraphs of G, each isomorphic to Kr , with no edges joining any two of the subgraphs) equals the minimum number of cliques of G that meet all the r -cliques of G. When r = 1, this says that chordal graphs have independence number equal to the clique covering number. When r = 2, this is equivalent to a result of Cameron (1989), and it implies a well known forbidden subgraph characterization of split graphs. In this paper we consider a weighted version of the above min-max optimization problem. Given a chordal graph G, with a nonnegative weight for each r -clique in G ,w eseek a set of independent r -cliques with maximum total weight. We present two algorithms to solve this problem, based on the principle of complementary slackness. The first one operates on a graph derived from G, and is an adaptation of an algorithm of Farber (1982). The second one improves the performance by reducing the number of constraints of the linear programs. Both results produce a min-max relation. When the algorithms are specialized to the situation in which all the r -cliques have the same weight, we simplify the algorithms reported in Hell et al. (2004), although these simpler algorithms are not as efficient. As a byproduct, we also obtain new elementary proofs of the above min-max result.

We describe a simple representation for the modules of a graph G. We show that the modules of G are in one-to-one correspondence with the ideals of certain posets. These posets are characterized and shown to be layered posets, that is, transitive closures of bipartite tournaments. Additionaly, we describe applications of the representation. Employing the above correspondence, we present methods for solving the following problems: (i) generate all modules of G, (ii) count the number of modules of G, (iii) find a maximal module satisfying some hereditary property of G and (iv) find a connected non-trivial module of G.