Now showing items 1-20 of 52

    • Approximately Coloring Graphs Without Long Induced Paths 

      Chudnovsky, Maria; Schaudt, Oliver; Spirkl, Sophie; stein, maya; Zhong, Mingxian (Springer Nature, 2019)
      It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable ...
    • Bi-objective short-term scheduling in a rolling horizon framework: a priori approaches with alternative operational objectives 

      Lee, Do Yeon; Fukasawa, Ricardo; Ricardez-Sandoval, Luis (Elsevier, 2019-11)
      This study addresses short-term scheduling problems with throughput and make-span as conflicting objectives, focusing on a priori multi-objective methods. Two contributions are presented. The first contribution is to propose ...
    • Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and Fan-Out Two 

      Held, Stephan; Spirkl, Sophie (Association for Computing Machinery, 2018-01)
      We consider the problem of constructing fast and small binary adder circuits. Among widely used adders, the Kogge-Stone adder is often considered the fastest, because it computes the carry bits for two n-bit numbers (where ...
    • Caterpillars in Erdős–Hajnal 

      Liebenau, Anita; Pilipczuk, Marcin; Seymour, Paul; Spirkl, Sophie (Elsevier, 2019-05)
      Let T be a tree such that all its vertices of degree more than two lie on one path; that is, T is a caterpillar subdivision. We prove that there exists ε > 0 such that for every graph G with |V(G)| ≥ 2 not containing T as ...
    • Colouring perfect graphs with bounded clique number 

      Chudnovsky, Maria; Lagoutte, Aurélie; Seymour, Paul; Spirkl, Sophie (Elsevier, 2017-01)
      A graph is perfect if the chromatic number of every induced subgraph equals the size of its largest clique, and an algorithm of Grötschel, Lovász, and Schrijver [9] from 1988 finds an optimal colouring of a perfect graph ...
    • A Complete Multipartite Basis for the Chromatic Symmetric Function 

      Crew, Logan; Spirkl, Sophie (Society for Industrial and Applied Mathematics, 2021-11-15)
      In the vector space of symmetric functions, the elements of the basis of elementary symmetric functions are (up to a factor) the chromatic symmetric functions of disjoint unions of cliques. We consider their graph complements, ...
    • Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph 

      Hajebi, Sepehr; Li, Yanjia; Spirkl, Sophie (Society for Industrial and Applied Mathematics, 2022-08-30)
      For a positive integer r and graphs G and H, we denote by G+H the disjoint union of G and H and by rH the union of r mutually disjoint copies of H. Also, we say G is H-free if H is not isomorphic to an induced subgraph of ...
    • Concatenating Bipartite Graphs 

      Chudnovsky, Maria; Hompe, Patrick; Scott, Alex; Seymour, Paul; Spirkl, Sophie (The Electronic Journal of Combinatorics, 2022)
      Let x, y E (0, 1], and let A, B, C be disjoint nonempty stable subsets of a graph G, where every vertex in A has at least x |B| neighbors in B, and every vertex in B has at least y|C| neighbors in C, and there are no edges ...
    • A Counterexample to a Conjecture About Triangle-Free Induced Subgraphs of Graphs with Large Chromatic Number 

      Carbonero, Alvaro; Hompe, Patrick; Moore, Benjamin; Spirkl, Sophie (Elsevier ScienceDirect, 2023-01)
      We prove that for every n, there is a graph G with χ(G) ≥ n and ω(G) ≤ 3 such that every induced subgraph H of G with ω(H) ≤ 2 satisfies χ(H) ≤ 4.This disproves a well-known conjecture. Our construction is a digraph with ...
    • A deletion–contraction relation for the chromatic symmetric function 

      Crew, Logan; Spirkl, Sophie (Elsevier, 2020-10)
      We extend the definition of the chromatic symmetric function XG to include graphs G with a vertex-weight function w : V (G) --> N. We show how this provides the chromatic symmetric function with a natural deletion-contraction ...
    • Detecting an Odd Hole 

      Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie (Association for Computing Machinery, 2020-02)
      We give a polynomial-time algorithm to test whether a graph contains an induced cycle with length more than three and odd.
    • Digraphs with All Induced Directed Cycles of the Same Length are not → χ -Bounded 

      Carbonero, Alvaro; Hompe, Patrick; Moore, Benjamin; Spirkl, Sophie (2022-10-07)
      For t > 2, let us call a digraph D t-chordal if all induced directed cycles in D have length equal to t. In an earlier paper, we asked for which t it is true that t-chordal graphs with bounded clique number have bounded ...
    • Disproportionate Division 

      Crew, Logan; Narayanan, Bhargav; Spirkl, Sophie (Wiley, 2020-10-01)
      We study the disproportionate version of the classical cake-cutting problem: how efficiently can we divide a cake, here [0,1], among n ≥ 2 agents with different demands α1, α2,..., αn summing to 1? When all the agents have ...
    • Edge coloring multigraphs without small dense subsets 

      Haxell, P.E.; Kierstead, H.A. (Elsevier, 2015-12-06)
      One consequence of a long-standing conjecture of Goldberg and Seymour about the chromatic index of multigraphs would be the following statement. Suppose $G$ is a multigraph with maximum degree $\Delta$, such that no vertex ...
    • Entropic Matroids and Their Representation 

      Abbe, Emmanuel; Spirkl, Sophie (Multidisciplinary Digital Publishing Institute, 2019)
      This paper investigates entropic matroids, that is, matroids whose rank function is given as the Shannon entropy of random variables. In particular, we consider p-entropic matroids, for which the random variables each have ...
    • Even pairs and prism corners in square-free Berge graphs 

      Chudnovsky, Maria; Maffray, Frédéric; Seymour, Paul; Spirkl, Sophie (Elsevier, 2018-07)
      Let G be a Berge graph such that no induced subgraph is a 4-cycle or a line-graph of a bipartite subdivision of K4. We show that every such graph G either is a complete graph or has an even pair.
    • Fast Prefix Adders for Non-uniform Input Arrival Times 

      Held, Stephan; Spirkl, Sophie (Springer Nature, 2017)
      We consider the problem of constructing fast and small parallel prefix adders for non-uniform input arrival times. In modern computer chips, adders with up to hundreds of inputs occur frequently, and they are often embedded ...
    • Finding an induced path that is not a shortest path 

      Berger, Eli; Seymour, Paul; Spirkl, Sophie (Elsevier, 2021-07)
      We give a polynomial-time algorithm that, with input a graph G and two vertices u; v of G, decides whether there is an induced uv-path that is longer than the shortest uv-path.
    • Finding Large H-Colorable Subgraphs in Hereditary Graph Classes 

      Chudnovsky, Maria; King, Jason; Pilipczuk, Michał; Rzążewski, Paweł; Spirkl, Sophie (Society for Industrial and Applied Mathematics, 2021-10-14)
      We study the Max Partial H-Coloring problem: given a graph G, find the largest induced subgraph of G that admits a homomorphism into H, where H is a fixed pattern graph without loops. Note that when H is a complete graph ...
    • Goldberg's conjecture is true for random multigraphs 

      Haxell, Penny; Krivelevich, Michael; Kronenberg, Gal (Elsevier, 2019-09)
      In the 70s, Goldberg, and independently Seymour, conjectured that for any multigraph G, the chromatic index χ′(G) satisfies χ′(G) ≤ max{∆(G)+1,⌈ρ(G)⌉}, where ρ(G) = max\{\frac {e(G[S])}{\lfloor|S|/2\rfloor} \mid S\subseteq ...

      UWSpace

      University of Waterloo Library
      200 University Avenue West
      Waterloo, Ontario, Canada N2L 3G1
      519 888 4883

      All items in UWSpace are protected by copyright, with all rights reserved.

      DSpace software

      Service outages