Source author record

Sophie Spirkl

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms Computational Geometry Hardware Architecture

Catalog footprint

Research overview

19works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs

Given a graph $G$ and a graph property $P$ we say that $G$ is minimal with respect to $P$ if no proper induced subgraph of $G$ has the property $P$ . An HC-obstruction is a minimal 2-connected non-Hamiltonian graph. Given a graph $H$ , a graph $G$ is $H$ -free if $G$ has no induced subgraph isomorphic to $H$ . The main motivation for this paper originates from a theorem of Duffus, Gould, and Jacobson (1981), which characterizes all the minimal connected graphs with no Hamiltonian path. In 1998, Brousek characterized all the claw-free HC-obstructions. On a similar note, Chiba and Furuya (2021), characterized all (not only the minimal) 2-connected non-Hamiltonian $\{K_{1,3}, N_{3,1,1}\}$ -free graphs. Recently, Cheriyan, Hajebi, and two of us (2022), characterized all triangle-free HC-obstructions and all the HC-obstructions which are split graphs. A wheel is a graph obtained from a cycle by adding a new vertex with at least three neighbors in the cycle. In this paper we characterize all the HC-obstructions which are wheel-free graphs.

preprint2022arXiv

A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

We prove that for every $n$ , there is a graph $G$ with $χ(G) \geq n$ and $ω(G) \leq 3$ such that every induced subgraph $H$ of $G$ with $ω(H) \leq 2$ satisfies $χ(H) \leq 4$ . This disproves a well-known conjecture. Our construction is a digraph with bounded clique number, large dichromatic number, and no induced directed cycles of odd length at least 5.

preprint2022arXiv

Bipartite graphs with no $K_6$ minor

A theorem of Mader shows that every graph with average degree at least eight has a $K_6$ minor, and this is false if we replace eight by any smaller constant. Replacing average degree by minimum degree seems to make little difference: we do not know whether all graphs with minimum degree at least seven have $K_6$ minors, but minimum degree six is certainly not enough. For every $c>0$ there are arbitrarily large graphs with average degree at least $8-c$ and minimum degree at least six, with no $K_6$ minor. But what if we restrict ourselves to bipartite graphs? The first statement remains true: for every $c>0$ there are arbitrarily large bipartite graphs with average degree at least $8-c$ and no $K_6$ minor. But surprisingly, going to minimum degree now makes a significant difference. We will show that every bipartite graph with minimum degree at least six has a $K_6$ minor. Indeed, it is enough that every vertex in the larger part of the bipartition has degree at least six.

preprint2022arXiv

Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth

A theta is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $\mathcal{H}$ of graphs, we say a graph $G$ is $\mathcal{H}$ -free if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$ . We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $c$ for which every (theta, triangle)-free graph $G$ has treewidth at most $c\log (|V(G)|)$ . A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)-free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth. Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $|V(G)|$ for every graph $G$ excluding the so-called three-path-configurations as well as a fixed complete graph. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and Coloring admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph.

preprint2022arXiv

Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs

In 1981, Duffus, Gould, and Jacobson showed that every connected graph either has a Hamiltonian path, or contains a claw ( $K_{1,3}$ ) or a net (a fixed six-vertex graph) as an induced subgraph. This implies that subject to being connected, these two are the only minimal (under taking induced subgraphs) graphs with no Hamiltonian path. Brousek (1998) characterized the minimal graphs that are $2$ -connected, non-Hamiltonian and do not contain the claw as an induced subgraph. We characterize the minimal graphs that are $2$ -connected and non-Hamiltonian for two classes of graphs: (1) split graphs, (2) triangle-free graphs. We remark that testing for Hamiltonicity is NP-hard in both of these classes.

preprint2022arXiv

Plethysms of Chromatic and Tutte Symmetric Functions

Plethysm is a fundamental operation in symmetric function theory, derived directly from its connection with representation theory. However, it does not admit a simple combinatorial interpretation, and finding coefficients of Schur function plethysms is a major open question. In this paper, we introduce a graph-theoretic interpretation for any plethysm based on the chromatic symmetric function. We use this interpretation to give simple proofs of new and previously known plethystic identities, as well as chromatic symmetric function identities.

preprint2022arXiv

Polynomial bounds for chromatic number VII. Disjoint holes

A hole in a graph $G$ is an induced cycle of length at least four, and a $k$ -multihole in $G$ is a set of pairwise disjoint and nonadjacent holes. It is well known that if $G$ does not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any $k$ , if $G$ does not contain a $k$ -multihole, then its chromatic number is at most a polynomial function of its clique number. We show that the same result holds if we ask for all the holes to be odd or of length four; and if we ask for the holes to be longer than any fixed constant or of length four. This is part of a broader study of graph classes that are polynomially $χ$ -bounded.

preprint2022arXiv

Strengthening Rodl's theorem

What can be said about the structure of graphs that do not contain an induced copy of some graph H? Rodl showed in the 1980s that every H-free graph has large parts that are very dense or very sparse. More precisely, let us say that a graph F on n vertices is c-restricted if either F or its complement has maximum degree at most cn. Rodl proved that for every graph H, and every c>0, every H-free graph G has a linear-sized set of vertices inducing a c-restricted graph. We strengthen Rodl's result as follows: for every graph H, and all c>0, every H-free graph can be partitioned into a bounded number of subsets inducing c-restricted graphs.

preprint2021arXiv

Erdos-Hajnal for graphs with no 5-hole

The Erdos-Hajnal conjecture says that for every graph H there exists c>0 such that every graph G not containing H as an induced subgraph has a clique or stable set of cardinality at least |G|^c. We prove that this is true when H is a cycle of length five. We also prove several further results: for instance, that if C is a cycle and H is the complement of a forest, there exists c>0 such that every graph G containing neither of C,H as an induced subgraph has a clique or stable set of cardinality at least |G|^c.

preprint2021arXiv

Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix

For integer $n>0$ , let $f(n)$ be the number of rows of the largest all-0 or all-1 square submatrix of $M$ , minimized over all $n\times n$ $0/1$ -matrices $M$ . Thus $f(n)= O(\log n)$ . But let us fix a matrix $H$ , and define $f_H(n)$ to be the same, minimized over over all $n\times n$ $0/1$ -matrices $M$ such that neither $M$ nor its complement (that is, change all $0$ 's to $1$ 's and vice versa) contains $H$ as a submatrix. It is known that $f_H(n)\ge εn^c$ , where $c, ε>0$ are constants depending on $H$ . When can we take $c=1$ ? If so, then one of $H$ and its complement must be an acyclic matrix (that is, the corresponding bipartite graph is a forest). Korandi, Pach, and Tomon conjectured the converse, that $f_H(n)$ is linear in $n$ for every acyclic matrix $H$ ; and they proved it for certain matrices $H$ with only two rows. Their conjecture remains open, but we show $f_H(n)=n^{1-o(1)}$ for every acyclic matrix $H$ ; and indeed there is a $0/1$ -submatrix that is either $Ω(n)\times n^{1-o(1)}$ or $n^{1-o(1)}\times Ω(n)$ .

preprint2020arXiv

A Deletion-Contraction Relation for the Chromatic Symmetric Function

We extend the definition of the chromatic symmetric function $X_G$ to include graphs $G$ with a vertex-weight function $w : V(G) \rightarrow \mathbb{N}$ . We show how this provides the chromatic symmetric function with a natural deletion-contraction relation analogous to that of the chromatic polynomial. Using this relation we derive new properties of the chromatic symmetric function, and we give alternate proofs of many fundamental properties of $X_G$ .

preprint2020arXiv

Finding an induced path that is not a shortest path

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.

preprint2020arXiv

Finding large $H$ -colorable subgraphs in hereditary graph classes

We study the \textsc{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 on $k$ vertices, the problem reduces to finding the largest induced $k$ -colorable subgraph, which for $k=2$ is equivalent (by complementation) to \textsc{Odd Cycle Transversal}. We prove that for every fixed pattern graph $H$ without loops, \textsc{Max Partial $H$ -Coloring} can be solved: $\bullet$ in $\{P_5,F\}$ -free graphs in polynomial time, whenever $F$ is a threshold graph; $\bullet$ in $\{P_5,\textrm{bull}\}$ -free graphs in polynomial time; $\bullet$ in $P_5$ -free graphs in time $n^{\mathcal{O}(ω(G))}$ ; $\bullet$ in $\{P_6,\textrm{1-subdivided claw}\}$ -free graphs in time $n^{\mathcal{O}(ω(G)^3)}$ . Here, $n$ is the number of vertices of the input graph $G$ and $ω(G)$ is the maximum size of a clique in~ $G$ . Furthermore, combining the mentioned algorithms for $P_5$ -free and for $\{P_6,\textrm{1-subdivided claw}\}$ -free graphs with a simple branching procedure, we obtain subexponential-time algorithms for \textsc{Max Partial $H$ -Coloring} in these classes of graphs. Finally, we show that even a restricted variant of \textsc{Max Partial $H$ -Coloring} is $\mathsf{NP}$ -hard in the considered subclasses of $P_5$ -free graphs, if we allow loops on $H$ .

preprint2020arXiv

List-three-coloring $P_t$ -free graphs with no induced 1-subdivision of $K_{1,s}$

Let $s$ and $t$ be positive integers. We use $P_t$ to denote the path with $t$ vertices and $K_{1,s}$ to denote the complete bipartite graph with parts of size $1$ and $s$ respectively. The one-subdivision of $K_{1,s}$ is obtained by replacing every edge $\{u,v\}$ of $K_{1,s}$ by two edges $\{u,w\}$ and $\{v,w\}$ with a new vertex $w$ . In this paper, we give a polynomial-time algorithm for the list-three-coloring problem restricted to the class of $P_t$ -free graph with no induced 1-subdivision of $K_{1,s}$ .

preprint2020arXiv

Pure pairs. I. Trees and linear anticomplete pairs

The Erdos-Hajnal Conjecture asserts that for every graph H there is a constant c > 0 such that every graph G that does not contain H as an induced subgraph has a clique or stable set of cardinality at least |G|^c. In this paper, we prove a conjecture of Liebenau and Pilipczuk, that for every forest H there exists c > 0, such that every graph G contains either an induced copy of H, or a vertex of degree at least c|G|, or two disjoint sets of at least c|G| vertices with no edges between them. It follows that for every forest H there is c > 0 so that if G contains neither H nor its complement as an induced subgraph then there is a clique or stable set of cardinality at least |G|^c.

preprint2020arXiv

Pure pairs. II. Excluding all subdivisions of a graph

We prove for every graph H there exists a>0 such that, for every graph G with at least two vertices, if no induced subgraph of G is a subdivision of H, then either some vertex of G has at least a|G| neighbours, or there are two disjoint sets A,B of at least a|G| vertices such that no edge joins A and B. It follows that for every graph H, there exists c>0 such that for every graph G, if no induced subgraph of G or its complement is a subdivision of H, then G has a clique or stable set of cardinality at least |G|^c. This is related to the Erdos-Hajnal conjecture.

preprint2016arXiv

Approximately coloring graphs without long induced paths

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 graph without an induced path on $t$ vertices, computes a coloring with $\max\{5,2\lceil{\frac{t-1}{2}}\rceil-2\}$ many colors. If the input graph is triangle-free, we only need $\max\{4,\lceil{\frac{t-1}{2}}\rceil+1\}$ many colors. The running time of our algorithm is $O((3^{t-2}+t^2)m+n)$ if the input graph has $n$ vertices and $m$ edges.

preprint2014arXiv

Fast Prefix Adders for Non-Uniform Input Arrival Times

We consider the problem of constructing fast and small parallel prefix adders for non-uniform input arrival times. This problem arises whenever the adder is embedded into a more complex circuit, e. g. a multiplier. Most previous results are based on representing binary carry-propagate adders as so-called parallel prefix graphs, in which pairs of generate and propagate signals are combined using complex gates known as prefix gates. Adders constructed in this model usually minimize the delay in terms of these prefix gates. However, the delay in terms of logic gates can be worse by a factor of two. In contrast, we aim to minimize the delay of the underlying logic circuit directly. We prove a lower bound on the delay of a carry bit computation achievable by any prefix carry bit circuit and develop an algorithm that computes a prefix carry bit circuit with optimum delay up to a small additive constant. Furthermore, we use this algorithm to construct a small parallel prefix adder. Compared to existing algorithms we simultaneously improve the delay and size guarantee, as well as the running time for constructing prefix carry bit and adder circuits.

preprint2014arXiv

The guillotine approach for TSP with neighborhoods revisited

The Euclidean TSP with neighborhoods (TSPN) is the following problem: Given a set R of k regions, find a shortest tour that visits at least one point from each region. We study the special cases of disjoint, connected, alpha-fat regions (i.e., every region P contains a disk of diameter diam(P)/alpha) and disjoint unit disks. For the latter, Dumitrescu and Mitchell proposed an algorithm based on Mitchell's guillotine subdivision approach for the Euclidean TSP and claimed it to be a PTAS. However, their proof contains a severe gap, which we will close in the following. Bodlaender et al. remark that their techniques for the minimum corridor connection problem carry over to the TSPN and yield an alternative PTAS for this problem. For disjoint connected alpha-fat regions of varying size, Mitchell proposed a slightly different PTAS candidate. We will expose several further problems and gaps in this approach. Some of them we can close, but overall, for alpha-fat regions, the existence of a PTAS for the TSPN remains open.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Sophie Spirkl

Research overview

Is this your work?

19 publications

Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs

A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

Bipartite graphs with no $K_6$ minor

Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth

Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs

Plethysms of Chromatic and Tutte Symmetric Functions

Polynomial bounds for chromatic number VII. Disjoint holes

Strengthening Rodl's theorem

Erdos-Hajnal for graphs with no 5-hole

Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix

A Deletion-Contraction Relation for the Chromatic Symmetric Function

Finding an induced path that is not a shortest path

Finding large $H$ -colorable subgraphs in hereditary graph classes

List-three-coloring $P_t$ -free graphs with no induced 1-subdivision of $K_{1,s}$

Pure pairs. I. Trees and linear anticomplete pairs

Pure pairs. II. Excluding all subdivisions of a graph

Approximately coloring graphs without long induced paths

Fast Prefix Adders for Non-Uniform Input Arrival Times

The guillotine approach for TSP with neighborhoods revisited

See the researcher in context

Building this map preview

Sophie Spirkl

Research overview

Is this your work?

19 publications

Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs

A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

Bipartite graphs with no K6K_6K6​ minor

Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth

Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs

Plethysms of Chromatic and Tutte Symmetric Functions

Polynomial bounds for chromatic number VII. Disjoint holes

Strengthening Rodl's theorem

Erdos-Hajnal for graphs with no 5-hole

Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix

A Deletion-Contraction Relation for the Chromatic Symmetric Function

Finding an induced path that is not a shortest path

Finding large HHH-colorable subgraphs in hereditary graph classes

List-three-coloring Pt P_t Pt​-free graphs with no induced 1-subdivision of K1,s K_{1,s} K1,s​

Pure pairs. I. Trees and linear anticomplete pairs

Pure pairs. II. Excluding all subdivisions of a graph

Approximately coloring graphs without long induced paths

Fast Prefix Adders for Non-Uniform Input Arrival Times

The guillotine approach for TSP with neighborhoods revisited

See the researcher in context

Building this map preview

Bipartite graphs with no $K_6$ minor

Finding large $H$ -colorable subgraphs in hereditary graph classes

List-three-coloring $P_t$ -free graphs with no induced 1-subdivision of $K_{1,s}$