Université de Fribourg

Bicolored Matchings in Some Classes of Graphs

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

In: Graphs and Combinatorics, 2007, vol. 23, no. 1, p. 47-60

We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R| = n + 1 such that perfect matchings with k red edges exist for all k, 0 ≤ k ≤ n. Given two integers p...

Université de Fribourg

On a graph coloring problem arising from discrete tomography

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

In: Networks, 2008, vol. 51, no. 4, p. 256-267

An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph G = (V,E) and a family equation image of chains Pi together with vectors h(Pi) = (h1, . . . , hik), one wants to find a partition V1,…,Vk of V such that for each Pi and each color j, |Vj ∩ Pi| = hij. An interpretation in terms of scheduling is presented. We consider special cases of...

Université de Fribourg

Degree-constrained edge partitioning in graphs arising from discrete tomography

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

In: Journal of Graph Algorithms and Applications, 2009, vol. 13, no. 2, p. 99-118

Starting from the basic problem of reconstructing a 2-dimensional im- age given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k = 3 colors is open. Variations and special cases are considered for the case k = 3 colors where the graph corresponding to the union of some color classes (for instance colors 1...

Université de Fribourg

A note on chromatic properties of threshold graphs

Ries, Bernard ; de Werra, Dominique ; Zenklusen, Rico

In: Discrete Mathematics, 2012, vol. 312, no. 10, p. 1838-1843

In threshold graphs one may find weights for the vertices and a threshold value t such that for any subset S of vertices, the sum of the weights is at most the threshold t if and only if the set S is a stable (independent) set. In this note we ask a similar question about vertex colorings: given an integer p, when is it possible to find weights (in general depending on p) for the vertices and...

Université de Fribourg

Split-critical and uniquely split-colorable graphs

Ekim, Tina ; Ries, Bernard ; de Werra, Dominique

In: Discrete Mathematics and Theoretical Computer Science, 2010, vol. 12, no. 5, p. 1-24

The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring problem from the point of view of split-coloring, such as criticality and the uniqueness of the minimum split-coloring. We discuss some...

Université de Fribourg

Blockers and transversals in some subclasses of bipartite graphs : When caterpillars are dancing on a grid

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

In: Discrete Mathematics, 2010, vol. 310, p. 132-146

Given an undirected graph G=(V,E) with matching number \nu(G), a d-blocker is a subset of edges B such that \nu(/V,E\B))= d. While the associated decision problem is NP-complete in bipartite graphs we show how to construct efficiently minimum d-transversals and minimum d-blockers in the...

Université de Fribourg

d-Transversals of stable sets and vertex covers in weighted bipartite graphs

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

In: Journal of Discrete Algorithms, 2012, vol. 17, p. 95-102

Let G = (V , E) be a graph in which every vertex v ∈ V has a weight w(v)>=0 and a cost c(v) >=0. Let SG be the family of all maximum-weight stable sets in G. For any integer d 0, a minimum d-transversal in the graph G with respect to SG is a subset of vertices T ⊆ V of minimum total cost such that |T ∩ S| d for every S ∈ SG. In this paper, we present a polynomial-time algorithm to...

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