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...
|
In: 4OR, 2008, vol. 6, no. 2, p. 101-123
|
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: 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, 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 a...
|
In: Journal of Graph Theory, 2017, vol. 88, no. 1, p. 18-39
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...
|
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: 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...
|
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...
|
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...
|