BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
In this paper, we prove that the MaxCut problem is NP-complete on permutation graphs, settling a long-standing open problem that appeared in the 1985 column of the "Ongoing Guide to NP-completeness" by David S. Johnson.
A temporal graph G is a graph that changes with time. More specifically, it is a pair (G,λ) where G is a graph and λ is a function on the edges of G that describes when each edge e∈E(G) is active. Given vertices s,t∈V(G), a temporal s,t-path is a path in G that traverses edges in non-decreasing time; and if s,t are non-adjacent, then a temporal s,t-cut is a subset S⊆V(G)∖{s,t} whose removal destroys all temporal s,t-paths. It is known that Menger's Theorem does not hold on this context, i.e., that the maximum number of internally vertex disjoint temporal s,t-paths is not necessarily equal to the minimum size of a temporal s,t-cut. In a seminal paper, Kempe, Kleinberg and Kumar (STOC'2000) defined a graph G to be Mengerian if equality holds on (G,λ) for every function λ. They then proved that, if each edge is allowed to be active only once in (G,λ), then G is Mengerian if and only if G has no gem as topological minor. In this paper, we generalize their result by allowing edges to be active more than once, giving a characterization also in terms of forbidden structures. We additionally provide a polynomial time recognition algorithm.
Given a graph G and a digraph D whose vertices are the edges of G, we investigate the problem of finding a spanning tree of G that satisfies the constraints imposed by D. The restrictions to add an edge in the tree depend on its neighborhood in D. Here, we generalize previously investigated problems by also considering as input functions ℓ and u on E(G) that give a lower and an upper bound, respectively, on the number of constraints that must be satisfied by each edge. The produced feasibility problem is denoted by \texttt{G-DCST}, while the optimization problem is denoted by \texttt{G-DCMST}. We show that \texttt{G-DCST} is NP-complete even under strong assumptions on the structures of G and D, as well as on functions ℓ and u. On the positive side, we prove two polynomial results, one for \texttt{G-DCST} and another for \texttt{G-DCMST}, and also give a simple exponential-time algorithm along with a proof that it is asymptotically optimal under the Ð. Finally, we prove that other previously studied constrained spanning tree (\textsc{CST}) problems can be modeled within our framework, namely, the \textsc{Conflict CST}, the \textsc{Forcing CS, the \textsc{At Least One/All Dependency CST}, the \textsc{Maximum Degree CST}, the \textsc{Minimum Degree CST}, and the \textsc{Fixed-Leaves Minimum Degree CST}.
A temporal digraph G is a triple (G,γ,λ) where G is a digraph, γ is a function on V(G) that tells us the timestamps when a vertex is active, and λ is a function on E(G) that tells for each uv∈E(G) when u and v are linked. Given a static digraph G, and a subset R⊆V(G), a spanning branching with root R is a subdigraph of G that has exactly one path from R to each v∈V(G). In this paper, we consider the temporal version of Edmonds' classical result about the problem of finding k edge-disjoint spanning branchings respectively rooted at given R1,⋯,Rk. We introduce and investigate different definitions of spanning branchings, and of edge-disjointness in the context of temporal graphs. A branching B is vertex-spanning if the root is able to reach each vertex v of G at some time where v is active, while it is temporal-spanning if v can be reached from the root at every time where v is active. On the other hand, two branchings B1 and B2 are edge-disjoint if they do not use the same edge of G, and are temporal-edge-disjoint if they can use the same edge of G but at different times. This lead us to four definitions of disjoint spanning branchings and we prove that, unlike the static case, only one of these can be computed in polynomial time, namely the temporal-edge-disjoint temporal-spanning branchings problem, while the other versions are NP-complete, even under very strict assumptions.
Given a graph G, and a spanning subgraph H of G, a circular q-backbone k-coloring of (G,H) is a proper k-coloring c of G such that q≤∣c(u)−c(v)∣≤k−q, for every edge uv∈E(H). The circular q-backbone chromatic number of (G,H), denoted by CBCq(G,H), is the minimum integer k for which there exists a circular q-backbone k-coloring of (G,H). The Four Color Theorem implies that whenever G is planar, we have CBC2(G,H)≤8. It is conjectured that this upper bound can be improved to 7 when H is a tree, and to 6 when H is a matching. In this work, we show that: 1) if G is planar and has no C4 as subgraph, and H is a linear spanning forest of G, then CBC2(G,H)≤7; 2) if G is a plane graph having no two 3-faces sharing an edge, and H is a matching of G, then CBC2(G,H)≤6; and 3) if G is planar and has no C4 nor C5 as subgraph, and H is a mathing of G, then CBC2(G,H)≤5. These results partially answer questions posed by Broersma, Fujisawa and Yoshimoto (2003), and by Broersma, Fomin and Golovach (2007). It also points towards a positive answer for the Steinberg's Conjecture.
Given a proper coloring f of a graph G, a b-vertex in f is a vertex that is adjacent to every color class but its own. It is a b-coloring if every color class contains at least one b-vertex, and it is a fall-coloring if every vertex is a b-vertex. The b-chromatic number of G is the maximum integer b(G) for which G has a b-coloring with b(G) colors, while the fall-chromatic number and the fall-acromatic number of G are, respectively, the minimum and maximum integers f1(G),f2(G) for which G has a fall-coloring. In this article, we explore the concepts of b-homomorphisms and Type II homomorphisms, which generalize the concepts of b-colorings and fall-colorings, and present some meta-theorems concerning products of graphs. As a result, we derive some previously known facts about these metrics on graph products. We also give a negative answer to a question posed by Kaul and Mitillos about fall-colorings of perfect graphs.
A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of G is the maximum integer χb(G) for which G has a b-coloring with χb(G) colors. A graph G is b-continuous if G has a b-coloring with k colors, for every integer k in the interval [χ(G),χb(G)]. It is known that not all graphs are b-continuous. Here, we investigate whether the lexicographic product G[H] of b-continuous graphs G and H is also b-continuous. Using homomorphisms, we provide a new lower bound for χb(G[H]), namely χb(G[Kt]), where t=χb(H), and prove that if G[Kℓ] is b-continuous for every positive integer ℓ, then G[H] admits a b-coloring with k colors, for every k in the interval [χ(G[H]),χb(G[Kt])]. We also prove that G[Kℓ] is b-continuous, for every positive integer ℓ, whenever G is a P4-sparse graph, and we give further results on the b-spectrum of G[Kℓ], when G is chordal.
A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of G is the maximum integer b(G) for which G has a b-coloring with b(G) colors. A graph G is b-continuous if G has a b-coloring with k colors, for every integer k in the interval [χ(G),b(G)]. It is known that not all graphs are b-continuous. In this article, we show that if G has girth at least 10, then G is b-continuous.
A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to at least one vertex in each other color class. The b-chromatic number of G is the maximum integer b(G) for which G has a b-coloring with b(G) colors. This problem was introduced by Irving and Manlove in 1999, where they showed that computing b(G) is NP-hard in general and polynomial-time solvable for trees. Since then, a number of complexity results were shown, including NP-hardness results for chordal graphs (Havet et. al., 2011) and line graphs (Campos et. al., 2015). In this article, we present a polynomial time algorithm that solves the problem restricted to claw-free block graphs, an important subclass of chordal graphs and line graphs. This is equivalent to solving the edge coloring version of the problem restricted to trees.
A proper k-coloring of a graph G=(V,E) is a function c:V(G)→{1,…,k} such that c(u)=c(v), for every uv∈E(G). The chromatic number χ(G) is the minimum k such that there exists a proper k-coloring of G. Given a spanning subgraph H of G, a q-backbone k-coloring of (G,H) is a proper k-coloring c of V(G) such that ∣c(u)−c(v)∣≥q, for every edge uv∈E(H). The q-backbone chromatic number BBCq(G,H) is the smallest k for which there exists a q-backbone k-coloring of (G,H). In this work, we show that every connected graph G has a generating tree T such that BBCq(G,T)=max{χ(G),⌈2χ(G)⌉+q}, and that this value is the best possible. As a direct consequence, we get that every connected graph G has a spanning tree T for which BBC2(G,T)=χ(G), if χ(G)≥4, or BBC2(G,T)=χ(G)+1, otherwise. Thus, by applying the Four Color Theorem, we have that every connected nonbipartite planar graph G has a spanning tree T such that BBC2(G,T)=4. This settles a question by Wang, Bu, Montassier and Raspaud (2012), and generalizes a number of previous partial results to their question.
In a recent article [5], the authors claim that the distance between the b-chromatic index of a tree and a known upper bound is at most 1. At the same time, in [7] the authors claim to be able to construct a tree where this difference is bigger than 1. However, the given example was disconnected, i.e., actually consisted of a forest. Here, we slightly modify their construction in order to produce trees, thus getting that indeed the difference between the b-chromatic index of trees and the known upper bound can be arbitrarily large. We also point out the mistake made in [5].
Given a finite field, one can form a directed graph using the field elements as vertices and connecting two vertices if their difference lies in a fixed subgroup of the multiplicative group. If -1 is contained in this fixed subgroup, then we obtain an undirected graph that is referred to as a generalized Paley graph. In this paper we study generalized Paley graphs whose clique and chromatic numbers coincide and link this theory to the study of the synchronization property in 1-dimensional primitive affine permutation groups.
A b-coloring of a graph is a coloring of its vertices such that every color class contains a vertex that has a neighbor in all other classes. The b-chromatic number of a graph is the largest integer k such that the graph has a b-coloring with k colors. We show how to compute in polynomial time the b-chromatic number of a graph of girth at least 9. This improves the seminal result of Irving and Manlove on trees.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.