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
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most 2 plus the maximum over all subgraphs of the difference between half the number of vertices and the independence number.
A strong edge-coloring of a graph G is an assignment of colors to edges such that every color class induces a matching. We here focus on bipartite graphs whose one part is of maximum degree at most 3 and the other part is of maximum degree Δ. For every such graph, we prove that a strong 4Δ-edge-coloring can always be obtained. Together with a result of Steger and Yu, this result confirms a conjecture of Faudree, Gyárfás, Schelp and Tuza for this class of graphs.
The Shortest Common Supersequence problem (SCS for short) consists in finding a shortest common supersequence of a finite set of words on a fixed alphabet Sigma. It is well-known that its decision version denoted [SR8] in [Garey and Johnson] is NP-complete. Many variants have been studied in the literature. In this paper we settle the complexity of two such variants of SCS where inputs do not contain identical consecutive letters. We prove that those variants denoted φSCS and MSCS both have a decision version which remains NP-complete when |Σ| is at least 3. Note that it was known for MSCS when |Σ| is at least 4 [Fleisher and Woeginger] and we discuss how [Darte] states a similar result for |Σ| at least 3.
Yannakakis' Clique versus Independent Set problem (CL-IS) in communication complexity asks for the minimum number of cuts separating cliques from stable sets in a graph, called CS-separator. Yannakakis provides a quasi-polynomial CS-separator, i.e. of size O(nlogn), and addresses the problem of finding a polynomial CS-separator. This question is still open even for perfect graphs. We show that a polynomial CS-separator almost surely exists for random graphs. Besides, if H is a split graph (i.e. has a vertex-partition into a clique and a stable set) then there exists a constant cH for which we find a O(ncH) CS-separator on the class of H-free graphs. This generalizes a result of Yannakakis on comparability graphs. We also provide a O(nck) CS-separator on the class of graphs without induced path of length k and its complement. Observe that on one side, cH is of order O(∣H∣log∣H∣) resulting from Vapnik-Chervonenkis dimension, and on the other side, ck is exponential. One of the main reason why Yannakakis' CL-IS problem is fascinating is that it admits equivalent formulations. Our main result in this respect is to show that a polynomial CS-separator is equivalent to the polynomial Alon-Saks-Seymour Conjecture, asserting that if a graph has an edge-partition into k complete bipartite graphs, then its chromatic number is polynomially bounded in terms of k. We also show that the classical approach to the stubborn problem (arising in CSP) which consists in covering the set of all solutions by O(nlogn) instances of 2-SAT is again equivalent to the existence of a polynomial CS-separator.
We prove that for every k, there exists ck>0 such that every graph G on n vertices not inducing a path Pk and its complement contains a clique or a stable set of size nck.
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.