1,721,521 research outputs found
Tree-Chromatic Number Is Not Equal to Path-Chromatic Number*
No full textFor a graph G and a tree-decomposition (T,B) of G, the chromatic number of (T,B) is the maximum of χ(G[B]), taken over all bags B∈B. The tree-chromatic number of G is the minimum chromatic number of all tree-decompositions (T,B) of G. The path-chromatic number of G is defined analogously. In this article, we introduce an operation that always increases the path-chromatic number of a graph. As an easy corollary of our construction, we obtain an infinite family of graphs whose path-chromatic number and tree-chromatic number are different. This settles a question of Seymour (J Combin Theory Ser B 116 (2016), 229–237). Our results also imply that the path-chromatic numbers of the Mycielski graphs are unbounded
The matroid secretary problem for minor-closed classes and random matroids
No full textWe prove that for every proper minor-closed class M of Fp-representable matroids, there exists an O(1)-competitive algorithm for the matroid secretary problem onM. This result relies on the extremely powerful matroid minor structure theory being developed by Geelen, Gerards, and Whittle. We also note that, for asymptotically almost all matroids, the matroid secretary algorithm that selects a random basis, ignoring weights, is (2 + o(1))-competitive. In fact, assuming the conjecture that almost all matroids are paving, there is a (1 + o(1))-competitive algorithm for almost all matroids
On the Erdős-Pósa property for long holes in C_4-free graphs
No full textWe prove that there exists a function f(k)=O(k^2logk) such that for every C4-free graph G and every k∈N, G either contains k vertex-disjoint holes of length at least 6, or a set X of at most f(k) vertices such that G−X has no hole of length at least 6. This answers a question of Kim and Kwon [Erdős-Pósa property of chordless cycles and its applications. JCTB 2020
Tree densities in sparse graph classes
No full textWhat is the maximum number of copies of a fixed forest T in an n-vertex graph in a graph class as ? We answer this question for a variety of sparse graph classes. In particular, we show that the answer is where is the size of the largest stable set in the subforest of T induced by the vertices of degree at most d, for some integer d that depends on. For example, when is the class of k-degenerate graphs then; when is the class of graphs containing no -minor then; and when is the class of k-planar graphs then. All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs
A Unified Erdős–Pósa Theorem for Constrained Cycles
Full text linkA (Γ 1 ,Γ 2 )-labeled graph is an oriented graph with its edges labeled by elements of the direct sum of two groups Γ 1 ,Γ 2 . A cycle in such a labeled graph is (Γ 1 ,Γ 2 )-non-zero if it is non-zero in both coordinates. Our main result is a generalization of the Flat Wall Theorem of Robertson and Seymour to (Γ 1 ,Γ 2 )-labeled graphs. As an application, we determine all canonical obstructions to the Erdős–Pósa property for (Γ 1 ,Γ 2 )-non-zero cycles in (Γ 1 ,Γ 2 )-labeled graphs. The obstructions imply that the half-integral Erdős–Pósa property always holds for (Γ 1 ,Γ 2 )-non-zero cycles. Moreover, our approach gives a unified framework for proving packing results for constrained cycles in graphs. For example, as immediate corollaries we recover the Erdős–Pósa property for cycles and S-cycles and the half-integral Erdős–Pósa property for odd cycles and odd S-cycles. Furthermore, we recover Reed's Escher-wall Theorem. We also prove many new packing results as immediate corollaries. For example, we show that the half-integral Erdős–Pósa property holds for cycles not homologous to zero, odd cycles not homologous to zero, and S-cycles not homologous to zero. Moreover, the (full) Erdős–Pósa property holds for S 1 -S 2 -cycles and cycles not homologous to zero on an orientable surface. Finally, we also describe the canonical obstructions to the Erdős–Pósa property for cycles not homologous to zero and for odd S-cycles
The biclique covering number of grids
No full textWe determine the exact value of the biclique covering number for all grid graphs
On Hilbert bases of cuts
No full textA Hilbert basis is a set of vectors X ⊆ Rd such that the integer cone (semigroup) generated by X is the intersection of the lattice generated by X with the cone generated by X. Let H be the class of graphs whose set of cuts is a Hilbert basis in RE (regarded as {0,1}-characteristic vectors indexed by edges). We show that H is not closed under edge deletions, subdivisions, nor 2-sums. Furthermore, no graph having K6 \ e as a minor belongs to H. This corrects an error in Laurent (1996). For positive results, we give conditions under which the 2-sum of two graphs produces a member of H. Using these conditions we show that all K5⊥-minor-free graphs are in H, where K5⊥ is the unique 3-connected graph obtained by uncontracting an edge of K5. We also establish a relationship between edge deletion and subdivision. Namely, if G′ is obtained from G ∈ H by subdividing e two or more times, then G \ e ∈ H if and only if G′ ∈ H
Intertwining connectivities in representable matroids
No full textLet M be a representable matroid and Q,R, S, T subsets of the ground set such that the smallest separation that separates Q from R has order k, and the smallest separation that separates S from T has order l. We prove that if M is sufficiently large, then there is an element e such that in one of M\e and M/e both connectivities are preserved. For matroids representable over a finite field we prove a stronger result: we show that we can remove e such that both a connectivity and a minor of M are preserved. © 2014 Society for Industrial and Applied Mathematics
Strengthening convex relaxations of 0/1-sets using Boolean formulas
No full textIn convex integer programming, various procedures have been developed to strengthen convex relaxations of sets of integer points. On the one hand, there exist several general-purpose methods that strengthen relaxations without specific knowledge of the set S of feasible integer points, such as popular linear programming or semi-definite programming hierarchies. On the other hand, various methods have been designed for obtaining strengthened relaxations for very specific sets S that arise in combinatorial optimization. We propose a new efficient method that interpolates between these two approaches. Our procedure strengthens any convex set containing a set S⊆ { 0 , 1 } n by exploiting certain additional information about S. Namely, the required extra information will be in the form of a Boolean formula φ defining the target set S. The new relaxation is obtained by “feeding” the convex set into the formula φ. We analyze various aspects regarding the strength of our procedure. As one application, interpreting an iterated application of our procedure as a hierarchy, our findings simplify, improve, and extend previous results by Bienstock and Zuckerberg on covering problems
- …
