A simplified construction is presented for Komjáth's result that for every uncountable cardinal κ $\kappa $, there are 2
κ ${2}^{\kappa }$ graphs of size κ $\kappa $ none of them being a minor of ...another.
Applying a recent extension (2015) of a structure theorem of Robertson, Seymour and Thomas from 1993, in this paper we establish Robertson's magic-tree conjecture from 1997.
On Andreae's ubiquity conjecture Carmesin, Johannes
Journal of combinatorial theory. Series B,
September 2023, 2023-09-00, Letnik:
162
Journal Article
Recenzirano
Odprti dostop
A graph H is ubiquitous if every graph G that for every natural number n contains n vertex-disjoint H-minors contains infinitely many vertex-disjoint H-minors. Andreae conjectured that every locally ...finite graph is ubiquitous. We give a disconnected counterexample to this conjecture. It remains open whether every connected locally finite graph is ubiquitous.
Nash-Williams' Strong Immersion Conjecture states that graphs are well-quasi-ordered by the strong immersion relation. That is, given infinitely many graphs, one graph contains another graph as a ...strong immersion. In this paper we study the analogous problem for directed graphs. It is known that digraphs are not well-quasi-ordered by the strong immersion relation, but for all known such infinite antichains, paths that change direction arbitrarily many times can be found. This paper proves that the converse statement is true: for every positive integer k, the digraphs that do not contain a path that changes direction k times are well-quasi-ordered by the strong immersion relation, even when vertices are labeled by a well-quasi-order. This result is optimal for classes of digraphs closed under taking subgraphs since paths that change direction arbitrarily many times with vertex-labels form an infinite antichain with respect to the strong immersion relation.
The micro-world of cographs Alecu, Bogdan; Lozin, Vadim; de Werra, Dominique
Discrete Applied Mathematics,
05/2022, Letnik:
312
Journal Article
Recenzirano
Odprti dostop
Cographs constitute a small point in the atlas of graph classes. However, by zooming in on this point, we discover a complex world, where many parameters jump from finiteness to infinity. In the ...present paper, we identify several milestones in the world of cographs and create a hierarchy of graph parameters grounded on these milestones.
We discover new hereditary classes of graphs that are minimal (with respect to set inclusion) of unbounded clique-width. The new examples include split permutation graphs and bichain graphs. Each of ...these classes is characterised by a finite list of minimal forbidden induced subgraphs. These, therefore, disprove a conjecture due to Daligault, Rao and Thomassé from 2010 claiming that all such minimal classes must be defined by infinitely many forbidden induced subgraphs.
In the same paper, Daligault, Rao and Thomassé make another conjecture that every hereditary class of unbounded clique-width must contain a labelled infinite antichain. We show that the two example classes we consider here satisfy this conjecture. Indeed, they each contain a canonical labelled infinite antichain, which leads us to propose a stronger conjecture: that every hereditary class of graphs that is minimal of unbounded clique-width contains a canonical labelled infinite antichain.
Abstract
The class of bipartite permutation graphs enjoys many nice and important properties. In particular, this class is critically important in the study of clique‐ and rank‐width of graphs, ...because it is one of the minimal hereditary classes of graphs of unbounded clique‐ and rank‐width. It also contains a number of important subclasses, which are critical with respect to other parameters, such as graph lettericity or shrub‐depth, and with respect to other notions, such as well‐quasi‐ordering or complexity of algorithmic problems. In the present paper we identify critical subclasses of bipartite permutation graphs of various types.
Multigraphs without large bonds are wqo by contraction Kamiński, Marcin; Raymond, Jean‐Florent; Trunck, Théophile
Journal of graph theory,
August 2018, 2018-08-00, 20180801, 2018-08, Letnik:
88, Številka:
4
Journal Article
Recenzirano
Odprti dostop
We show that the class of multigraphs with at most p connected components and bonds of size at most k is well‐quasi‐ordered by edge contraction for all positive integers p,k. (A bond is a minimal ...nonempty edge cut.) We also characterize canonical antichains for this relation.
We prove that the strong immersion order is a well‐quasi‐ordering on the class of semicomplete digraphs, thereby strengthening a result of Chudnovsky and Seymour (2011, J. Comb. Theory, Series B, ...101, 47–53) that this holds for the class of tournaments.
PDF
