Refine my results

Document type

Institution

Specific Collection

Language

Domain

Keyword

Université de Fribourg

Claw-free graphs with strongly perfect complements : Fractional and integral version, Part II: Nontrivial strip-structures

Chudnovsky, Maria ; Ries, Bernard ; Zwols, Yori

In: Discrete applied mathematics, 2011, vol. 159, no. 17, p. 1996-2029

Strongly perfect graphs have been studied by several authors (e.g., Berge and Duchet (1984) [1], Ravindra (1984) [7] and Wang (2006) [8]). In a series of two papers, the current paper being the second one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the...

Université de Fribourg

Claw-free graphs with strongly perfect complements : Fractional and integral version. Part I. Basic graphs

Chudnovsky, Maria ; Ries, Bernard ; Zwols, Yori

In: Discrete Applied Mathematics, 2011, vol. 159, no. 17, p. 1971-1995

Strongly perfect graphs have been studied by several authors (e.g. Berge and Duchet (1984) [1], Ravindra (1984) [12] and Wang (2006) [14]). In a series of two papers, the current paper being the first one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement....

Université de Fribourg

Proper circular arc graphs as intersection graphs of pathson a grid

Galby, Esther ; Mazzoleni, María Pía ; Ries, Bernard

In: Discrete Applied Mathematics, 2019, vol. 262, p. 195-202

In this paper we present a characterization, by an infinite family of minimal forbidden induced subgraphs, of proper circular arc graphs which are intersection graphs of paths on a grid, where each path has at most one bend (turn).

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