In: Discrete Applied Mathematics, 2021, vol. 290, p. 17-35
In this paper we continue the systematic study of Contact graphs of Paths on a Grid (CPG graphs) initiated in Deniz et al. (2018). A CPG graph is a graph for which there exists a collection of pairwise interiorly disjoint paths on a grid in one-to-one correspondence with its vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. If every...
|
In: Probability Theory and Related Fields, 2015, vol. 161, no. 1-2, p. 351-427
|
In: Algorithmica, 2015, vol. 71, no. 2, p. 354-376
|
In: Discrete & Computational Geometry, 2015, vol. 53, no. 4, p. 703-712
|
In: Discrete Mathematics, 2021, vol. 344, no. 1, p. 112169
In this work, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k > 0? We show that for k = 1 (resp. k = 2), the problem is NP-hard (resp. coNP-hard). We further prove that for k = 1, the problem is W[1]-hard parameterized by domination number plus the mim-width of the input...
|
In: European Journal of Operational Research, 2015, vol. 240, no. 2, p. 307-314
In this paper we present the Selective Graph Coloring Problem, a generalization of the standard graph col-oring problem as well as several of its possible applications. Given a graph with a partition of its vertex set into several clusters, we want to select one vertex per cluster such that the chromatic number of the subgraph induced by the selected vertices is minimum. This problem appeared...
|
In: European Journal of Operational Research, 2011, vol. 210, no. 2, p. 169-175
Given a graph G =(V, E), a satisfying bisection of G is a partition of the vertex set V into two sets V1, V2, such that |V1| = |V2|, and such that every vertex v in V has at least as many neighbors in its own set as in the other set. The problem of deciding whether a graph G admits such a partition is NP-complete. In Bazgan et al. (2008) [C. Bazgan, Z. Tuza, D. Vanderpooten, Approximation of...
|
In: Discrete Mathematics, 2012, vol. 312, no. 2, p. 427-440
In this paper we consider graphs G whose vertices can be represented as single-bend paths (i.e., paths with at most one turn) on a rectangular grid, such that two vertices are adjacent in G if and only if the corresponding paths share at least one edge of the grid. These graphs, called B1-EPG graphs, were first introduced in Golumbic et al. (2009) [13]. Here we show that the neighborhood of every...
|
In: Discrete Mathematics, 2012, vol. 312, no. 7, p. 1372-1385
The vertex colouring problem is known to be NP-complete in the class of triangle-free graphs. Moreover, it is NP-complete in any subclass of triangle-free graphs defined by a finite collection of forbidden induced subgraphs, each of which contains a cycle. In this paper, we study the vertex colouring problem in subclasses of triangle-free graphs obtained by forbidding graphs without cycles, i.e.,...
|
In: Developmental Psychology, 2020, vol. 56, p. 261-274
Toddlers’ understanding of object rotation was investigated using a multi-method approach. Participants were 44 toddlers between 22 and 38 months of age. In an eye-tracking task, they observed a shape that rotated and disappeared briefly behind an occluder. In an object-fitting task, they rotated wooden blocks and fit them through apertures. Results of the eye-tracking task showed that with...
|