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 prove that for every tree T of radius h, there is an integer c such that every T-minor-free graph is contained in H⊠Kc for some graph H with pathwidth at most 2h−1. This is a qualitative strengthening of the Excluded Tree Minor Theorem of Robertson and Seymour (GM I). We show that radius is the right parameter to consider in this setting, and 2h−1 is the best possible bound.
Weak coloring numbers generalize the notion of degeneracy of a graph. They were introduced by Kierstead \& Yang in the context of games on graphs. Recently, several connections have been uncovered between weak coloring numbers and various parameters studied in graph minor theory and its generalizations. In this note, we show that for every fixed k≥1, the maximum r-th weak coloring number of a graph with simple treewidth k is Θ(rk−1logr). As a corollary, we improve the lower bound on the maximum r-th weak coloring number of planar graphs from Ω(r2) to Ω(r2logr), and we obtain a tight bound of Θ(rlogr) for outerplanar graphs.
We study problems related to colouring bottomless rectangles. One of our main results shows that for any positive integers m,k, there is no semi-online algorithm that can k-colour bottomless rectangles with disjoint boundaries in increasing order of their top sides, so that any m-fold covered point is covered by at least two colours. This is, surprisingly, a corollary of a stronger result for arborescence colourings. Any semi-online colouring algorithm that colours an arborescence in leaf-to-root order with a bounded number of colours produces arbitrarily long monochromatic paths. This is complemented by optimal upper bounds given by simple online colouring algorithms from other directions. Our other main results study configurations of bottomless rectangles in an attempt to improve the \textit{polychromatic k-colouring number}, mk∗. We show that for many families of bottomless rectangles, such as unit-width bottomless rectangles, mk∗ is linear in k. We also present an improved lower bound for general families: mk∗≥2k−1.
We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath, Leighton and Rosenberg from 1992. The key to the proof is a new structural tool called layered partitions, and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. (2004) that graphs in a proper minor-closed class have low treewidth colourings.
We prove the conjecture of Seymour (1993) that for every apex-forest H1 and outerplanar graph H2 there is an integer p such that every 2-connected graph of pathwidth at least p contains H1 or H2 as a minor. An independent proof was recently obtained by Dang and Thomas.
We investigate the behavior of Boolean dimension with respect to components and blocks. To put our results in context, we note that for Dushnik-Miller dimension, we have that if dim(C)≤d for every component C of a poset P, then dim(P)≤max{2,d}; also if dim(B)≤d for every block B of a poset P, then dim(P)≤d+2. By way of constrast, local dimension is well behaved with respect to components, but not for blocks: if ldim(C)≤d for every component C of a poset P, then ldim(P)≤d+2; however, for every d≥4, there exists a poset P with ldim(P)=d and dim(B)≤3 for every block B of P. In this paper we show that Boolean dimension behaves like Dushnik-Miller dimension with respect to both components and blocks: if bdim(C)≤d for every component C of P, then bdim(P)≤2+d+4⋅2d; also if bdim(B)≤d for every block of P, then bdim(P)≤19+d+18⋅2d.
In 1977, Trotter and Moore proved that a poset has dimension at most 3 whenever its cover graph is a forest, or equivalently, has treewidth at most 1. On the other hand, a well-known construction of Kelly shows that there are posets of arbitrarily large dimension whose cover graphs have treewidth 3. In this paper we focus on the boundary case of treewidth 2. It was recently shown that the dimension is bounded if the cover graph is outerplanar (Felsner, Trotter, and Wiechert) or if it has pathwidth 2 (Biró, Keller, and Young). This can be interpreted as evidence that the dimension should be bounded more generally when the cover graph has treewidth 2. We show that it is indeed the case: Every such poset has dimension at most 1276.
We show that posets of bounded height whose cover graphs exclude a fixed graph as a topological minor have bounded dimension. This result was already proven by Walczak. However, our argument is entirely combinatorial and does not rely on structural decomposition theorems. Given a poset with large dimension but bounded height, we directly find a large clique subdivision in its cover graph. Therefore, our proof is accessible to readers not familiar with topological graph theory, and it allows us to provide explicit upper bounds on the dimension. With the introduced tools we show a second result that is supporting a conjectured generalization of the previous result. We prove that (k+k)-free posets whose cover graphs exclude a fixed graph as a topological minor contain only standard examples of size bounded in terms of k.
In the concurrent graph sharing game, two players, called First and Second, share the vertices of a connected graph with positive vertex-weights summing up to 1 as follows. The game begins with First taking any vertex. In each proceeding round, the player with the smaller sum of collected weights so far chooses a non-taken vertex adjacent to a vertex which has been taken, i.e., the set of all taken vertices remains connected and one new vertex is taken in every round. (It is assumed that no two subsets of vertices have the same sum of weights.) One can imagine the players consume their taken vertex over a time proportional to its weight, before choosing a next vertex. In this note we show that First has a strategy to guarantee vertices of weight at least 1/3 regardless of the graph and how it is weighted. This is best-possible already when the graph is a cycle. Moreover, if the graph is a tree First can guarantee vertices of weight at least 1/2, which is clearly best-possible.
The existence of an on-line competitive algorithm for coloring bipartite graphs remains a tantalizing open problem. So far there are only partial positive results for bipartite graphs with certain small forbidden graphs as induced subgraphs. We propose a new on-line competitive coloring algorithm for P9-free bipartite graphs.
We study on-line colorings of certain graphs given as intersection graphs of objects "between two lines", i.e., there is a pair of horizontal lines such that each object of the representation is a connected set contained in the strip between the lines and touches both. Some of the graph classes admitting such a representation are permutation graphs (segments), interval graphs (axis-aligned rectangles), trapezoid graphs (trapezoids) and cocomparability graphs (simple curves). We present an on-line algorithm coloring graphs given by convex sets between two lines that uses O(ω3) colors on graphs with maximum clique size ω. In contrast intersection graphs of segments attached to a single line may force any on-line coloring algorithm to use an arbitrary number of colors even when ω=2. The {\em left-of} relation makes the complement of intersection graphs of objects between two lines into a poset. As an aside we discuss the relation of the class C of posets obtained from convex sets between two lines with some other classes of posets: all 2-dimensional posets and all posets of height 2 are in C but there is a 3-dimensional poset of height 3 that does not belong to C. We also show that the on-line coloring problem for curves between two lines is as hard as the on-line chain partition problem for arbitrary posets.
Over the last 30 years, researchers have investigated connections between dimension for posets and planarity for graphs. Here we extend this line of research to the structural graph theory parameter tree-width by proving that the dimension of a finite poset is bounded in terms of its height and the tree-width of its cover graph.
For positive integers w and k, two vectors A and B from Zw are called k-crossing if there are two coordinates i and j such that A[i]−B[i]≥k and B[j]−A[j]≥k. What is the maximum size of a family of pairwise 1-crossing and pairwise non-k-crossing vectors in Zw? We state a conjecture that the answer is kw−1. We prove the conjecture for w≤3 and provide weaker upper bounds for w≥4. Also, for all k and w, we construct several quite different examples of families of desired size kw−1. This research is motivated by a natural question concerning the width of the lattice of maximum antichains of a partially ordered set.
We give new positive results on the long-standing open problem of geometric covering decomposition for homothetic polygons. In particular, we prove that for any positive integer k, every finite set of points in R^3 can be colored with k colors so that every translate of the negative octant containing at least k^6 points contains at least one of each color. The best previously known bound was doubly exponential in k. This yields, among other corollaries, the first polynomial bound for the decomposability of multiple coverings by homothetic triangles. We also investigate related decomposition problems involving intervals appearing on a line. We prove that no algorithm can dynamically maintain a decomposition of a multiple covering by intervals under insertion of new intervals, even in a semi-online model, in which some coloring decisions can be delayed. This implies that a wide range of sweeping plane algorithms cannot guarantee any bound even for special cases of the octant problem.
We give a simple argument showing that the number of edges in the intersection graph G of a family of n sets in the plane with a linear union-complexity is O(ω(G)n). In particular, we prove χ(G)≤col(G)<19ω(G) for intersection graph G of a family of pseudo-discs, which improves a previous bound.
We consider straight-line outerplanar drawings of outerplanar graphs in which a small number of distinct edge slopes are used, that is, the segments representing edges are parallel to a small number of directions. We prove that Δ−1 edge slopes suffice for every outerplanar graph with maximum degree Δ≥4. This improves on the previous bound of O(Δ5), which was shown for planar partial 3-trees, a superclass of outerplanar graphs. The bound is tight: for every Δ≥4 there is an outerplanar graph with maximum degree Δ that requires at least Δ−1 distinct edge slopes in an outerplanar straight-line drawing.
Several classical constructions illustrate the fact that the chromatic number of a graph can be arbitrarily large compared to its clique number. However, until very recently, no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set X in R2 that is not an axis-aligned rectangle and for any positive integer k produces a family F of sets, each obtained by an independent horizontal and vertical scaling and translation of X, such that no three sets in F pairwise intersect and χ(F)>k. This provides a negative answer to a question of Gyarfas and Lehel for L-shapes. With extra conditions, we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries, and equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.
In the 1970s, Erdos asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is no. Specifically, for each positive integer k, we construct a triangle-free family of line segments in the plane with chromatic number greater than k. Our construction disproves a conjecture of Scott that graphs excluding induced subdivisions of any fixed graph have chromatic number bounded by a function of their clique number.
We prove that for any point set P in the plane, a triangle T, and a positive integer k, there exists a coloring of P with k colors such that any homothetic copy of T containing at least ck^8 points of P, for some constant c, contains at least one of each color. This is the first polynomial bound for range spaces induced by homothetic polygons. The only previously known bound for this problem applies to the more general case of octants in R^3, but is doubly exponential.
A nonrepetitive coloring of a path is a coloring of its vertices such that the sequence of colors along the path does not contain two identical, consecutive blocks. The remarkable construction of Thue asserts that 3 colors are enough to color nonrepetitively paths of any length. A nonrepetitive coloring of a graph is a coloring of its vertices such that all simple paths are nonrepetitively colored. Assume that each vertex v of a graph G has assigned a set (list) of colors Lv. A coloring is chosen from {Lv}v∈V(G) if the color of each v belongs to Lv. The Thue choice number of G, denoted by πl(G), is the minimum k such that for any list assignment {Lv} of G with each ∣Lv∣≥k there is a nonrepetitive coloring of G chosen from {Lv}. Alon et al. (2002) proved that πl(G)=O(Δ2) for every graph G with maximum degree at most Δ. We propose an almost linear bound in Δ for trees, namely for any $\epsi>0$ there is a constant c such that $π_l(T)\leq cΔ^{1+\epsi}$ for every tree T with maximum degree Δ. The only lower bound for trees is given by a recent result of Fiorenzi et al. (2011) that for any Δ there is a tree T such that πl(T)=Ω(loglogΔlogΔ). We also show that if one allows repetitions in a coloring but still forbid 3 identical consecutive blocks of colors on any simple path, then a constant size of the lists allows to color any tree.
The on-line choice number of a graph is a variation of the choice number defined through a two person game. It is at least as large as the choice number for all graphs and is strictly larger for some graphs. In particular, there are graphs G with ∣V(G)∣=2χ(G)+1 whose on-line choice numbers are larger than their chromatic numbers, in contrast to a recently confirmed conjecture of Ohba that every graph G with ∣V(G)∣≤2χ(G)+1 has its choice number equal its chromatic number. Nevertheless, an on-line version of Ohba conjecture was proposed in [P. Huang, T. Wong and X. Zhu, Application of polynomial method to on-line colouring of graphs, European J. Combin., 2011]: Every graph G with ∣V(G)∣≤2χ(G) has its on-line choice number equal its chromatic number. This paper confirms the on-line version of Ohba conjecture for graphs G with independence number at most 3. We also study list colouring of complete multipartite graphs K3⋆k with all parts of size 3. We prove that the on-line choice number of K3⋆k is at most 3/2k, and present an alternate proof of Kierstead's result that its choice number is ⌈(4k−1)/3⌉. For general graphs G, we prove that if ∣V(G)∣≤χ(G)+χ(G) then its on-line choice number equals chromatic number.
A sequence is nonrepetitive if it does not contain two adjacent identical blocks. The remarkable construction of Thue asserts that 3 symbols are enough to build an arbitrarily long nonrepetitive sequence. It is still not settled whether the following extension holds: for every sequence of 3-element sets L1,...,Ln there exists a nonrepetitive sequence s1,...,sn with si∈Li. Applying the probabilistic method one can prove that this is true for sufficiently large sets Li. We present an elementary proof that sets of size 4 suffice (confirming the best known bound). The argument is a simple counting with Catalan numbers involved. Our approach is inspired by a new algorithmic proof of the Lovász Local Lemma due to Moser and Tardos and its interpretations by Fortnow and Tao. The presented method has further applications to nonrepetitive games and nonrepetitive colorings of graphs.
Given two players alternately picking pieces of a pizza sliced by radial cuts, in such a way that after the first piece is taken every subsequent chosen piece is adjacent to some previously taken piece, we provide a strategy for the starting player to get 4/9 of the pizza. This is best possible and settles a conjecture of Peter Winkler.
(Note. The results of this manuscript has been merged and published with another paper of the same authors: A new approach to nonrepetitve sequences.) A repetition of size h (h⩾1) in a given sequence is a subsequence of consecutive terms of the form: xx=x1...xhx1...xh. A sequence is nonrepetitive if it does not contain a repetition of any size. The remarkable construction of Thue asserts that 3 different symbols are enough to build an arbitrarily long nonrepetitive sequence. We consider game-theoretic versions of results on nonrepetitive sequences. A nonrepetitive game is played by two players who pick, one by one, consecutive terms of a sequence over a given set of symbols. The first player tries to avoid repetitions, while the second player, in contrast, wants to create them. Of course, by simple imitation, the second player can force lots of repetitions of size 1. However, as proved by Pegden, there is a strategy for the first player to build an arbitrarily long sequence over 37 symbols with no repetitions of size >1. Our techniques allow to reduce 37 to 6. Another game we consider is an erase-repetition game. Here, whenever a repetition occurs, the repeated block is immediately erased and the next player to move continues the play. We prove that there is a strategy for the first player to build an arbitrarily long nonrepetitive sequence over 8 symbols. Our approach is inspired by a new algorithmic proof of the Lovász Local Lemma due to Moser and Tardos and previous work of Moser (his so called entropy compression argument).
On-line chain partition is a two-player game between Spoiler and Algorithm. Spoiler presents a partially ordered set, point by point. Algorithm assigns incoming points (immediately and irrevocably) to the chains which constitute a chain partition of the order. The value of the game for orders of width w is a minimum number $\fVal(w)$ such that Algorithm has a strategy using at most $\fVal(w)$ chains on orders of width at most w. We analyze the chain partition game for up-growing semi-orders. Surprisingly, the golden ratio comes into play and the value of the game is ⌊21+5w⌋.
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.