Affiner les résultats

Collection spécifique


Université de Fribourg

On the minimum and maximum selective graph coloring problems in some graph classes

Ries, Bernard

In: Discrete Applied Mathematics, 2016, vol. 204, p. 77-89

Given a graph together with a partition of its vertex set, the minimum selective coloring problem consists of selecting one vertex per partition set such that the chromatic number of the subgraph induced by the selected vertices is minimum. The contribution of this paper is twofold. First, we investigate the complexity status of the minimum selective coloring problem in some specific graph...

Accès public à partir du 20 févr. 2021
Université de Fribourg

Classifying k-edge colouring for H-free graphs

Galby, Esther ; T. Lima, Paloma ; Paulusma, Daniël ; Ries, Bernard

In: Information procesing letters, 2019, vol. 146, p. 39-43

A graph is H-free if it does not contain an induced subgraph isomorphic to H. For every integer k and every graph H, we determine the computational complexity of k-Edge Colouring for H-free graphs.

Accès public à partir du 22 juin 2020
Université de Fribourg

Contraction and deletion blockers for perfect graphs and H-free graphs

Y. Diner, Öznur ; Paulusma, Daniël ; Picouleau, Christophe ; Ries, Bernard

In: Theoretical computer science, 2018, vol. 746, p. 49-72

We study the following problem: for given integers d, k and graph G, can we reduce some fixed graph parameter π of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic number χ, clique number ω and independence number α, and as operations we choose edge contraction ec and vertex deletion vd. We determine the complexity of this problem...

Université de Fribourg

Coloring some classes of mixed graphs

Ries, Bernard

In: Discrete Applied Mathematics, 2007, vol. 155, no. 1, p. 1-6

We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs.A mixed coloring c is a coloring such that for every edge [xi, xj], c(xi ) ≠ c(xj ) and for every arc (xp, xq ), c(xp)

Université de Fribourg

Complexity of two coloring problems in cubic planar bipartite mixed graphs

Ries, Bernard

In: Discrete Applied Mathematics, 2010, vol. 158, no. 5, p. 592-596

In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].

Université de Fribourg

Upper Domination : Towards a Dichotomy Through Boundary Properties

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

In: Algorithmica, 2018, vol. 80, no. 10, p. 2799-2817

Anupper dominating set in a graph is a minimal dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard.We study the complexity of this problem in finitely defined classes of graphs and conjecture that the problem admits a complexity dichotomy in this family. A helpful tool to study the complexity of an algorithmic problem is the notion of...

Université de Fribourg

On star and biclique edge-colorings

Dantas, Simone ; Groshaus, Marina ; Guedes , André ; C.S. Machado, Raphael ; Ries, Bernard ; Sasaki, Diana

In: International Transactions in Operational Research, 2017, vol. 24, p. 339-346

A biclique of G is a maximal set of vertices that induces a complete bipartite subgraph Kp,q of G with at least one edge, and a star of a graph G is a maximal set of vertices that induces a complete bipartite graph K1,q. A biclique (resp. star) edge-coloring is a coloring of the edges of a graph with no monochromatic bicliques (resp. stars). We prove that the problem of determining whether a...

Université de Fribourg

Dominating induced matchings in graphs containing no long claw

Hertz, Alain ; Lozin, Vadim ; Ries, Bernard ; Zamaraev, Viktor ; de Werra, Dominique

In: Journal of Graph Theory, 2017, vol. 88, no. 1, p. 1-23

An induced matching 𝑀 in a graph 𝐺 is dominating if every edge not in 𝑀 shares exactly one vertex with an edge in 𝑀. The DOMINATING INDUCED MATCHING problem (also known as EFFICIENT EDGE DOMINATION) asks whether a graph 𝐺 contains a dominating induced matching. This problem is generally NP-complete, but polynomial-time solvable for graphs with some special properties. In...

Université de Fribourg

On the ratio between maximum weight perfect matchings and maximum weight matchings in grids

Fonseca, Guilherme D. da ; Ries, Bernard ; Sasaki, Diana

In: Discrete Applied Mathematics, 2016, vol. 207, p. 45–55

Given a graph G that admits a perfect matching, we investigate the parameter η(G) (originally motivated by computer graphics applications) which is defined as follows. Among all nonnegative edge weight assignments, η(G) is the minimum ratio between (i) the maximum weight of a perfect matching and (ii) the maximum weight of a general matching. In this paper, we determine the exact value of η...