查看更多>>摘要：We prove that every graph has a canonical tree of tree decompositions that distinguishes all principal tangles (these include the ends and various kinds of large finite dense structures) efficiently. Here 'trees of tree-decompositions' are a slightly weaker notion than 'tree-decompositions' but much more wellbehaved than 'tree-like metric spaces'. This theorem is best possible in the sense that we give an example that 'trees of tree-decompositions' cannot be strengthened to 'tree decompositions' in the above theorem. This implies results of Dunwoody and Kron as well as of Carmesin, Diestel, Hundertmark and Stein. Beyond that for locally finite graphs our result gives for each k is an element of N canonical tree-decompositions that distinguish all k-distinguishable ends efficiently. (c) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：Hajos conjectured that every graph containing no subdivision of the complete graph Ks+1 is properly s-colorable. This conjecture was disproved by Catlin. Indeed, the maximum chromatic number of such graphs is Omega(s(2)/logs). We prove that O(s) colors are enough for a weakening of this conjecture that only requires every monochromatic component to have bounded size (so-called clustered coloring). Our approach leads to more results, many of which only require a much weaker assumption that forbids an 'almost (<= 1)-subdivision' (where at most one edge is subdivided more than once). This assumption is best possible, since no bound on the number of colors exists unless we allow at least one edge to be subdivided arbitrarily many times. We prove the following (where s >= 2): 1. Graphs of bounded treewidth and with no almost (<= 1)-subdivision of Ks+1 are s-choosable with bounded clustering. 2. For every graph H, graphs with no H -minor and no almost (<= 1)-subdivision of Ks+1 are (s + 1)-colorable with bounded clustering. 3. For every graph H of maximum degree at most d, graphs with no H -sub division and no almost (<= 1)-subdivision of Ks+1 are max{s + 3d - 5, 2}-colorable with bounded clustering. 4. For every graph H of maximum degree d, graphs with no Ks,t subgraph and no H -sub division are max{s + 3d - 4, 2}-colorable with bounded clustering. 5. Graphs with no Ks+1-subdivision are (4s - 5)-colorable with bounded clustering. The first result is tight and shows that the clustered analogue of Hajos' conjecture is true for graphs of bounded treewidth. The second result implies an upper bound for the clustered version of Hadwiger's conjecture that is only one color away from the known lower bound, and shows that the number of colors is independent of the forbidden minor. The final result is the first O(s) bound on the clustered chromatic number of graphs with no Ks+1-sub division. (C) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：A B S T R A C T This paper discusses a family of graphs, called PraegerXu graphs and denoted PX(n, k) here, introduced by C.E. Praeger and M.-Y. Xu in 1989. These tetravalent graphs are distinguished by having large symmetry groups; their vertex-stabilizers can be arbitrarily larger than the number of vertices in the graph. This paper does the following: (1) exhibits a connection between vertex-transitive groups of symmetries in a Praeger-Xu graph and certain linear codes, (2) characterizes those linear codes, (3) characterizes PraegerXu graphs PX(n, k) which are Cayley, (4) shows that every PX(n, k) is quasi-Cayley, and (5) constructs an infinite family of Praeger-Xu graphs in which a smallest vertex-transitive group of symmetries has arbitrarily large vertex-stabiliser. (c) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：Generalizing a graph-theoretical result of Maffray to binary matroids, Oxley and Wetzler proved that a connected simple binary matroid M has no odd circuits other than triangles if and only if M is affine, M is isomorphic to M(K-4) or F-7, or M is the cycle matroid of a graph consisting of a collection of triangles all sharing a common edge. In this paper, we show that if M is a 3-connected binary matroid having a 5-element circuit but no larger odd circuit, then M has rank less than six; or M has rank six and is one of nine sporadic matroids; or M can be obtained by attaching together, via generalized parallel connection across a common triangle, a collection of copies of F-7 and M(K-4) and then possibly deleting up to two elements of the common triangle. From this, we deduce that a 3-connected simple graph with a 5-cycle but no larger odd cycle is obtained from K-3,K-n for some n >= 3 by adding one, two, or three edges between the vertices in the 3-vertex class. (C) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：A graph transformation called the compression of a graph G is known to decrease the number of spanning trees, the all terminal reliability, and the magnitude of the coefficients of the chromatic polynomial of a graph G. All of these graph parameters can be derived from the Tutte polynomial of G, and in this paper we determine more generally compression's effect on the Tutte polynomial, recovering the previous results and obtaining similar results for a wide variety of other graph parameters derived from the Tutte polynomial. Since any simple connected graph can be transformed into a connected threshold graph via a series of compressions, this gives that threshold graphs are extremal simple graphs for all of the parameters considered. (c) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：The topic is the average order of a connected induced subgraph of a graph. This generalizes, to graphs in general, the average order of a subtree of a tree. In 1983, Jamison proved that the average order of a subtree, over all trees of order n, is minimized by the path P-n. In 2018, Kroeker, Mol, and Oellermann conjectured that P-n minimizes the average order of a connected induced subgraph over all connected graphs. The main result of this paper confirms this conjecture. (C) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：Since first introduced by Sudakov and Vu in 2008, the study of resilience problems in random graphs received a lot of attention in probabilistic combinatorics. Of particular interest are resilience problems of spanning structures. It is known that for spanning structures which contain many triangles, local resilience cannot prevent an adversary from destroying all copies of the structure by removing a negligible amount of edges incident to every vertex. In this paper we generalise the notion of local resilience to H-resilience and demonstrate its usefulness on the containment problem of the square of a Hamilton cycle. In particular, we show that there exists a constant C > 0 such that if p >= C log(3) n/root n, then w.h.p. in every subgraph G of a random graph G(n,p) there exists the square of a Hamilton cycle, provided that every vertex of G remains on at least a (4/9+o(1))-fraction of its triangles from G(n,p). The constant 4/9 is optimal and the value of p slightly improves on the best-known appearance threshold of such a structure and is optimal up to the logarithmic factor. (C) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：Let r >= 4 be an integer and consider the following game on the complete graph K-n for n is an element of rZ: Two players, Maker and Breaker, alternately claim previously unclaimed edges of K-n such that in each turn Maker claims one and Breaker claims b is an element of N edges. Maker wins if her graph contains a K-r-factor, that is a collection of n/r vertex-disjoint copies of K-r, and Breaker wins otherwise. In other words, we consider a b-biased K-r-factor Maker-Breaker game. We show that the threshold bias for this game is of order n(2)/((r+2)). This makes a step towards determining the threshold bias for making bounded-degree spanning graphs and extends a result of Allen et al. who resolved the case r is an element of {3, 4} up to a logarithmic factor. (C) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs. (c) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：We prove that any quasirandom dense large graph in which all degrees are equal and even can be decomposed into any given collection of two-factors (2-regular spanning subgraphs). A special case of this result gives a new solution to the Oberwolfach problem. (c) 2021 Elsevier Inc. All rights reserved.
NSTL
Elsevier