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
Neumann-Lara conjectured in 1985 that every planar digraph with digirth at least three is 2-colourable, meaning that the vertices can be 2-coloured without creating any monochromatic directed cycles. We prove a relaxed version of this conjecture: every planar digraph of digirth at least four is 2-colourable.
Scott proved in 1997 that for any tree T, every graph with bounded clique number which does not contain any subdivision of T as an induced subgraph has bounded chromatic number. Scott also conjectured that the same should hold if T is replaced by any graph H. Pawlik et al. recently constructed a family of triangle-free intersection graphs of segments in the plane with unbounded chromatic number (thereby disproving an old conjecture of Erdős). This shows that Scott's conjecture is false whenever H is obtained from a non-planar graph by subdividing every edge at least once. It remains interesting to decide which graphs H satisfy Scott's conjecture and which do not. In this paper, we study the construction of Pawlik et al. in more details to extract more counterexamples to Scott's conjecture. For example, we show that Scott's conjecture is false for any graph obtained from K4 by subdividing every edge at least once. We also prove that if G is a 2-connected multigraph with no vertex contained in every cycle of G, then any graph obtained from G by subdividing every edge at least twice is a counterexample to Scott's conjecture.
Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. We disprove this conjecture.
We examine cooperative games where the viability of a coalition is determined by whether or not its members have the ability to communicate amongst themselves independently of non-members. This necessary condition for viability was proposed by Myerson (1977) and is modeled via an interaction graph G=(V,E); a coalition S⊆V is then viable if and only if the induced graph G[S] is connected. The non-emptiness of the core of a coalition game can be tested by a well-known covering LP. Moreover, the integrality gap of its dual packing LP defines exactly the multiplicative least-core and the relative cost of stability of the coalition game. This gap is upper bounded by the packing-covering ratio which, for graphical coalition games, is known to be at most the treewidth of the interaction graph plus one (Meir et al. 2013). We examine the packing-covering ratio and integrality gaps of graphical coalition games in more detail. We introduce the thicket parameter of a graph, and prove it precisely measures the packing-covering ratio. It also approximately measures the primal and dual integrality gaps. The thicket number provides an upper bound of both integrality gaps. Moreover we show that for any interaction graph, the primal integrality gap is, in the worst case, linear in terms of the thicket number while the dual integrality gap is polynomial in terms of it. At the heart of our results, is a graph theoretic minmax theorem showing the thicket number is equal to the minimum width of a vine decomposition of the coalition graph (a vine decomposition is a generalization of a tree decomposition). We also explain how the thicket number relates to the VC-dimension of the set system produced by the game.
In this paper we show how to combine two algorithmic techniques to obtain linear time algorithms for various optimization problems on graphs, and present a subroutine which will be useful in doing so. The first technique is iterative shrinking. In the first phase of an iterative shrinking algorithm, we construct a sequence of graphs of decreasing size G1,…,Gℓ where G1 is the initial input, Gℓ is a graph on which the problem is easy, and Gi is obtained from Gi+1 via some shrinking algorithm. In the second phase we work through the sequence in reverse, repeatedly constructing a solution for a graph from the solution for its successor. In an iterative compaction algorithm, we insist that the graphs decrease by a constant fraction of the entire graph. Another approach to solving optimization problems is to exploit the structural properties implied by the connectivity of the input graph. This approach can be used on graphs which are not highly connected by decomposing an input graph into its highly connected pieces, solving subproblems on these specially structured pieces and then combining their solutions. We combine these two techniques by developing compaction algorithms which when applied to the highly connected pieces preserve their connectivity properties. The structural properties this connectivity implies can be helpful both in finding further compactions in later iterations and when we are manipulating solutions in the second phase of an iterative compaction algorithm. To illustrate how this compaction algorithm can be used as a subroutine, we present a linear time algorithm that given four vertices {s1,s2,t1,t2} of a graph G, either finds a pair of disjoint paths P1 and P2 of G such that Pi has endpoints si and ti, or returns a planar embedding of an auxiliary graph which shows that no such pair exists.
We provide a new lower bound on the minimum distance of a family of quantum LDPC codes based on Cayley graphs proposed by MacKay, Mitchison and Shokrollahi. Our bound is exponential, improving on the quadratic bound of Couvreur, Delfosse and Zémor. This result is obtained by examining a family of subsets of the hypercube which locally satisfy some parity conditions.
We improve complexity bounds for energy-efficient speed scheduling problems for both the single processor and multi-processor cases. Energy conservation has become a major concern, so revisiting traditional scheduling problems to take into account the energy consumption has been part of the agenda of the scheduling community for the past few years. We consider the energy minimizing speed scaling problem introduced by Yao et al. where we wish to schedule a set of jobs, each with a release date, deadline and work volume, on a set of identical processors. The processors may change speed as a function of time and the energy they consume is the αth power of its speed. The objective is then to find a feasible schedule which minimizes the total energy used. We show that in the setting with an arbitrary number of processors where all work volumes are equal, there is a 2(1+ε)(5(1+ε))α−1B~α=Oα(1) approximation algorithm, where B~α is the generalized Bell number. This is the first constant factor algorithm for this problem. This algorithm extends to general unequal processor-dependent work volumes, up to losing a factor of (2(1+r)r)α in the approximation, where r is the maximum ratio between two work volumes. We then show this latter problem is APX-hard, even in the special case when all release dates and deadlines are equal and r is 4. In the single processor case, we introduce a new linear programming formulation of speed scaling and prove that its integrality gap is at most 12α−1. As a corollary, we obtain a (12(1+ε))α−1 approximation algorithm where there is a single processor, improving on the previous best bound of 2α−1(1+ε)αB~α when α≥25.
A class of graphs closed under taking induced subgraphs is χ-bounded if there exists a function f such that for all graphs G in the class, χ(G)≤f(ω(G)). We consider the following question initially studied in [A. Gy{á}rf{á}s, Problems from the world surrounding perfect graphs, {\em Zastowania Matematyki Applicationes Mathematicae}, 19:413--441, 1987]. For a χ-bounded class C, is the class Cˉ χ-bounded (where Cˉ is the class of graphs formed by the complements of graphs from C)? We show that if C is χ-bounded by the constant function f(x)=3, then Cˉ is χ-bounded by g(x)=⌊58x⌋ and this is best possible. We show that for every constant c>0, if C is χ-bounded by a function f such that f(x)=x for x≥c, then Cˉ is χ-bounded. For every j, we construct a class of graphs χ-bounded by f(x)=x+x/logj(x) whose complement is not χ-bounded.
Given a directed graph D = (V,A) we define its intersection graph I(D) = (A,E) to be the graph having A as a node-set and two nodes of I(D) are adjacent if their corresponding arcs share a common node that is the tail of at least one of these arcs. We call these graphs facility location graphs since they arise from the classical uncapacitated facility location problem. In this paper we show that facility location graphs are hard to recognize and they are easy to recognize when the graph is triangle-free. We also determine the complexity of the vertex coloring, the stable set and the facility location problems on that class.
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.