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: Theoretical computer science, 2018, vol. 746, p. 49-72
We study the following problem: for given integers d, k and graph G, can we reduce some fixed graph parameter π of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic number χ, clique number ω and independence number α, and as operations we choose edge contraction ec and vertex deletion vd. We determine the complexity of this problem...
|
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: Discrete applied mathematics, 2019, vol. 257, p. 361-367
A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by one. We consider the problems of deciding whether a graph has a critical vertex or edge, respectively. We give a complexity dichotomy for both problems restricted to H-free graphs, that is, graphs with no induced subgraph isomorphic to H. Moreover, we show that an edge is critical if and only if...
|
In: Lecture Notes in Computer Science, 2016, vol. 9849, p. 38-49
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, 2017, vol. 10185, p. 470-483
Let d and k be two given integers, and let G be a graph. Can we reduce the independence number of G by at least d via at most k graph operations from some fixed set S? This problem belongs to a class of so-called blocker problems. It is known to be co-NP-hard even if S consists of either an edge contraction or a vertex deletion. We further investigate its computational complexity under these...
|
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...
|
