Refine my results

Language

Domain

Université de Fribourg

On Split B1-EPG Graphs

Deniz, Zakir ; Nivelle, Simon ; Ries, Bernard ; Schindl, David

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
Université de Fribourg

Characterising Chordal Contact : Bo-VPG Graphs

Bonomo, Flavia ; Mazzoleni, Maria Pia ; Rean, Mariano Leonardo ; Ries, Bernard

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...

Université de Fribourg

On two coloring problems in mixed graphs

Ries, Bernard ; de Werra, Dominique

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....

Université de Fribourg

Blockers and transversals

Zenklusen, Rico ; Ries, Bernard ; Picouleau, Christophe ; de Werra, Dominique ; Costa, Marie-Christine ; Bentz, Cédric

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...

Université de Fribourg

Graph coloring with cardinality constraints on the neighborhoods

Costa, Marie-Christine ; de Werra, Dominique ; Picouleau, Christophe ; Ries, Bernard

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...

Université de Fribourg

Mixed graph edge coloring

Furmańczyk, Hanna ; Kosowski, Adrian ; Ries, Bernard ; Żyliński, Paweł

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
Université de Fribourg

Graphs vertex-partitionable into strong cliques

Hujdurović, Ademir ; Milanič, Martin ; Ries, Bernard

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...

Université de Fribourg

A Boundary Property for Upper Domination

AbouEisha, Hassan ; Hussain, Shahid ; Lozin, Vadim ; Monnot, Jérôme ; Ries, Bernard ; Zamaraev, Viktor

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...

Université de Fribourg

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

Paulusma, Daniël ; Picouleau, Christophe ; Ries, Bernard

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...

Università della Svizzera italiana

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

Mapelli, Sarah Natalia ; Krause, Rolf (Dir.) ; Catapano, Carlo V. (Codir.)

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...