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....
|
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...
|
In: Algorithmic Operations Research, 2010, vol. 5, p. 75-85
Consider a project which consists in a set of operations to be performed, assuming the processing time of each operation is at most one time period. In this project, precedence and incompatibility constraints between operations have to be satisfied. The goal is to assign a time period to each operation while minimizing the duration of the whole project and while taking into account all the...
|
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...
|
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...
|
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).
|
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...
|
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...
|
In: European Journal of Combinatorics, 2008, vol. 29, p. 712-725
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. For...
|
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...
|
