# Refine my results

## On Split B1-EPG Graphs

### In: Lecture Notes in Computer Science, 2018, vol. 10807, p. 361-375

We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the chromatic number and the clique number. We let the set S consist of either an edge contraction or a vertex deletion. As all these problems are...

Public access from Dec 18, 2019

## Characterising Chordal Contact : Bo-VPG Graphs

### In: Lecture Notes in Computer Science, 2018, vol. 10856, p. 89-100

A graph G is a Bo- VPG graph if it is the vertex intersection graph of horizontal and vertical paths on a grid. A graph G is a contact Bo- VPG graph if the vertices can be represented by interiorly disjoint horizontal or vertical paths on a grid and two vertices are adjacent if and only if the corresponding paths touch. In this paper, we present a minimal forbidden induced subgraph...

## On two coloring problems in mixed graphs

### In: European Journal of Combinatorics, 2008, vol. 29, p. 712-125

We are interested in coloring the vertices of a mixed graph, i.e., a graph containing edges and arcs. We consider two different coloring problems: in the first one, we want adjacent vertices to have different colors and the tail of an arc to get a color strictly less than a color of the head of this arc; in the second problem, we also allow vertices linked by an arc to have the same color....

## Blockers and transversals

### In: Discrete Mathematics, 2009, vol. 309, p. 4306-4314

Given an undirected graph G=(V,E) with matching number \nu(G), we define d- blockers as subsets of edges B such that \nu(G=(V,E\B))\leq \nu(G)-d. We define d- transversals T as subsets of edges such that every maximum matching M has |M\cap T|\geq d. We explore connections between d-blockers and d-transversals. Special classes of graphs are examined which include complete graphs, regular...

## Graph coloring with cardinality constraints on the neighborhoods

### In: discrete Optimization, 2009, vol. 6, no. 4, p. 362-369

Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph a k-coloring, i.e., a partition (V_1,\cdots,V_k) of the vertex set of G such that, for some specified neighborhood \tilde|{N}(v) of each vertex v, the number of vertices in \tilde|{N}(v)\cap V_i is (at most) a given integer h_i^v. The complexity of some...

## Mixed graph edge coloring

### In: Discrete Mathematics, 2009, vol. 309, no. 12, p. 4027-4036

We are interested in coloring the edges of a mixed graph, i.e., a graph containing unoriented and oriented edges. This problem is related to a communication problem in job-shop scheduling systems. In this paper we give general bounds on the number of required colors and analyze the complexity status of this problem. In particular, we provide NP-completeness results for the case of outerplanar...

Public access from Mar 5, 2020

## Graphs vertex-partitionable into strong cliques

### In: Discrete Mathematics, 2018, vol. 341, p. 1392-1405

A clique in a graph is strong if it intersects all maximal independent sets. A graph is localizable if it has a partition of the vertex set into strong cliques. Localizable graphs were introduced by Yamashita and Kameda in 1999 and form a rich class of well- covered graphs that coincides with the class of well-covered graphs within the class of perfect graphs. In this paper, we give several...

## A Boundary Property for Upper Domination

### In: Lecture Notes in Computer Science, 2016, vol. 9843, p. 229-240

An upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard, but can be solved in polynomial time in some restricted graph classes, such as P4-free graphs or 2K2-free graphs. For classes defined by finitely many forbidden induced subgraphs, the boundary separating...

## Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions

### In: Lecture Notes in Computer Science, 2016, vol. 9849, p. 38-49

We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the chromatic number and the clique number. We let the set S consist of either an edge contraction or a vertex deletion. As all these problems are...

## Deciphering the complexity of human noncoding promoter-proximal transcriptome : different scales of transcriptional control : from a single gene to the whole epigenome

### Thèse de doctorat : Università della Svizzera italiana, 2019 ; 2019INFO001.

Long noncoding RNAs (lncRNAs) have gained increasing interest in molecular studies, their active participation in important biological functions has emerged and their direct involvement in genomic reprogramming during development and diseases, including cancer, has been demonstrated. Several studies have shown their active contribution in transcriptional control and they are emerging as...