In: Mathematical Programming, 2015, vol. 149, no. 1-2, p. 361-390
|
In: European Journal of Operational Research, 2011, vol. 210, no. 2, p. 169-175
Given a graph G =(V, E), a satisfying bisection of G is a partition of the vertex set V into two sets V1, V2, such that |V1| = |V2|, and such that every vertex v in V has at least as many neighbors in its own set as in the other set. The problem of deciding whether a graph G admits such a partition is NP-complete. In Bazgan et al. (2008) [C. Bazgan, Z. Tuza, D. Vanderpooten, Approximation of...
|
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: 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: Mathematical Programming, 2014, vol. 146, no. 1-2, p. 525-554
|
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...
|
