Search

We characterize planar graphs and graph minors among other graph theoretic notions in terms of right-angled Artin groups (RAAGs). For this, we determine all sets of elements in RAAGs with ears as underlying graphs that are exactly the sets of vertex generators. Generalizing ear decompositions of graphs to loose ear decompositions, we characterize both decompositions in terms of RAAGs. The desired results follow as applications of loose ear decompositions of RAAGs. [ABSTRACT FROM AUTHOR]

We prove that for any ε > 0 , for any large enough t , there is a graph that admits no K t -minor but admits a (3 2 − ε) t -colouring that is "frozen" with respect to Kempe changes, i.e. any two colour classes induce a connected component. This disproves three conjectures of Las Vergnas and Meyniel from 1981. [ABSTRACT FROM AUTHOR]

We prove that a graph has an r -bounded subdivision of a wheel if and only if it does not have a graph-decomposition of locality r and width at most two. [ABSTRACT FROM AUTHOR]

We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al. [66] 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 properminorclosed classes. Second, we give a simple proof of the result by DeVos et al. [31] that graphs in a proper minorclosed class have low treewidth colourings. [ABSTRACT FROM AUTHOR]

The rotational dimension is a minor-monotone graph invariant related to the dimension of a Euclidean space containing a spectral embedding corresponding to the first nonzero eigenvalue of the graph Laplacian, which is introduced by Göring, Helmberg and Wappler. In this paper, we study rotational dimensions of graphs which contain large complete graphs. The complete graph is characterized by its rotational dimension. It will be obtained that a chordal graph may be made large while keeping the rotational dimension constant. [ABSTRACT FROM AUTHOR]

Let Oct 1 + and Oct 2 + be the planar and non-planar graphs, respectively, obtained from the Octahedron by 3-splitting a vertex. For Oct 1 + , we prove that if a 4-connected graph is Oct 1 + -minor-free, then it is C 6 2 , C 2 k + 1 2 (k ≥ 2) or it is obtained from C 5 2 by repeatedly 4-splitting vertices. We also show that a planar graph is Oct 1 + -minor-free if and only if it is constructed by repeatedly taking 0-, 1-, 2-sums starting from { K 1 , K 2 , K 3 } ∪ κ ∪ { O c t a h e d r o n , L 5 } , where κ is the set of graphs obtained by repeatedly taking the special 3-sums of K 4 and L 5 is the graph obtained from two 5-cycles a 1 a 2 ... a 5 a 1 , b 1 b 2 ... b 5 b 1 by adding the five edges a i b i for all 1 ≤ i ≤ 5. For Oct 2 + , we prove that if a 4-connected graph is Oct 2 + -minor-free, then it is planar, C 2 k + 1 2 (k ≥ 2) , the line graph of K 3 , 3 or it is obtained from C 5 2 by repeatedly 4-splitting vertices. [ABSTRACT FROM AUTHOR]

The classical Hadwiger conjecture dating back to 1940s states that any graph of chromatic number at least r has the clique of order r as a minor. Hadwiger's conjecture is an example of a well‐studied class of problems asking how large a clique minor one can guarantee in a graph with certain restrictions. One problem of this type asks what is the largest size of a clique minor in a graph on n vertices of independence number α(G) at most r. If true Hadwiger's conjecture would imply the existence of a clique minor of order n/α(G). Results of Kühn and Osthus and Krivelevich and Sudakov imply that if one assumes in addition that G is H‐free for some bipartite graph H then one can find a polynomially larger clique minor. This has recently been extended to triangle‐free graphs by Dvořák and Yepremyan, answering a question of Norin. We complete the picture and show that the same is true for arbitrary graph H, answering a question of Dvořák and Yepremyan. In particular, we show that any Ks‐free graph has a clique minor of order cs(n/α(G))1+110(s−2), for some constant cs depending only on s. The exponent in this result is tight up to a constant factor in front of the 1s−2 term. [ABSTRACT FROM AUTHOR]

For a given list assignment L of a graph G , an (L , r) -coloring of G is a proper coloring c such that for any vertex v with degree d (v) , v is adjacent to vertices of at least min { d (v) , r } different color with c (v) ∈ L (v). The r-hued list chromatic number of G , denoted as χ L , r (G) , is the least integer k , such that for any v ∈ V (G) and every list assignment L with | L (v) | = k , G has an (L , r) -coloring. Let K (r) = r + 3 if 2 ≤ r ≤ 3 , K (r) = ⌊ 3 r / 2 ⌋ + 1 if r ≥ 4. In Song et al. (2014), it is proved that if G is a K 4 -minor-free graph, then χ L , r (G) ≤ K (r) + 1. Let K 4 (n) be the set of all subdivisions of K 4 on n vertices. Utilizing the decompositions by Chen et al for K 4 (7) -minor free graphs in Chen et al. (2020), we prove that if G is a K 4 (7) -minor free graph, then χ L , r (G) ≤ K (r) + 1. [ABSTRACT FROM AUTHOR]

Minor-embedding heuristics have become an indispensable tool for compiling problems in quadratically unconstrained binary optimization (QUBO) into the hardware graphs of quantum and CMOS annealing processors. While recent embedding heuristics have been developed for annealers of moderate size (about 2000 nodes), the size of the latest CMOS annealing processor (with 102,400 nodes) poses entirely new demands on the embedding heuristic. This raises the question, if recent embedding heuristics can maintain meaningful embedding performance on hardware graphs of increasing size. Here, we develop an improved version of the probabilistic-swap-shift-annealing (PSSA) embedding heuristic [which has recently been demonstrated to outperform the standard embedding heuristic by D-Wave Systems (Cai et al. in http://arxiv.org/abs/1406.2741, 2014)] and evaluate its embedding performance on hardware graphs of increasing size. For random cubic and Barábasi–Albert graphs we find the embedding performance of improved PSSA to consistently exceed the threshold of the best known complete graph embedding by a factor of 3.2 and 2.8, respectively, up to hardware graphs with 102,400 nodes. On the other hand, for random graphs with constant edge density not even improved PSSA can overcome the deterministic threshold guaranteed by the existence of the best known complete graph embedding. Finally, we prove a new upper bound on the maximal embeddable size of complete graphs into hardware graphs of CMOS annealers and show that the embedding performance of its currently best known complete graph embedding has optimal order for hardware graphs with fixed coordination number. [ABSTRACT FROM AUTHOR]

We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalizes a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class. [ABSTRACT FROM AUTHOR]

We prove the extremal function for K9= minors, where K9= denotes the complete graph K9 with two edges removed. In particular, we show that any graph with n≥8 vertices and at least 6n−20 edges either contains a K9= minor or is isomorphic to a graph obtained from disjoint copies of K8 and K2,2,2,2,2 by identifying cliques of size 5. We utilize computer assistance to prove one of our lemmas. [ABSTRACT FROM AUTHOR]

Hadwiger's conjecture claims that any graph with no Kt minor is (t−1)‐colorable. This has been proved for t≤6, but remains open for t≥7. As a variant of this conjecture, graphs with no Kt= minor have been considered, where Kt= denotes the complete graph with two edges removed. It has been shown that graphs with no Kt= minor are (2t−8)‐colorable for t∈{7,8}. In this paper, we extend this result to the case t=9 and show that graphs with no K9= minor are 10‐colorable. [ABSTRACT FROM AUTHOR]

In this paper, we extend two classical results about the density of subgraphs of hypercubes to subgraphs G of Cartesian products G1□⋯□Gm of arbitrary connected graphs. Namely, we show that (∣E(G)|/∣V(G)∣)≤⌈2max{dens(G1),...,dens(Gm)}⌉log∣V(G)∣, where dens(H) is the maximum ratio ∣E(H′)∣/∣V(H′)∣ taken over all subgraphs H′ of H. We introduce the notions of VC‐dimension VC‐dim⁡(G) and VC‐density VC‐dens(G) of a subgraph G of a Cartesian product G1□⋯□Gm, generalizing the classical Vapnik‐Chervonenkis dimension of set‐families (viewed as subgraphs of hypercubes). We prove that if G1,...,Gm belong to the class G(H) of all finite connected graphs not containing a given graph H as a minor, then for any subgraph G of G1□⋯□Gm the sharper inequality (∣E(G)∣/∣V(G)∣)≤μ(H)⋅VC‐dim⁡*(G) holds, where μ(H) is the supremum of the densities of the graphs from G(H). We refine and sharpen these two results to several specific graph classes. We also derive upper bounds (some of them polylogarithmic) for the size of adjacency labeling schemes of subgraphs of Cartesian products. [ABSTRACT FROM AUTHOR]

The max-cut problem is a fundamental and much-studied NP -hard combinatorial optimisation problem, with a wide range of applications. Several authors have shown that the max-cut problem can be solved in polynomial time if the underlying graph is free of certain minors. We give a polyhedral counterpart of these results. In particular, we show that, if a family of valid inequalities for the cut polytope satisfies certain conditions, then there is an associated minor-closed family of graphs on which the max-cut problem can be solved efficiently. [ABSTRACT FROM AUTHOR]

In this paper, we consider optimal 1-planar multigraphs, that is, n -vertex multigraph having exactly 4 n − 8 edges and a drawing on the sphere such that each edge crosses at most one other edge, and that the drawing has no 2-gonal face. We discuss the connectivity of optimal 1-planar multigraphs, and show a generating theorem of such graphs using some operations preserving optimal 1-planarity. Finally, we characterize optimal 1-planar multigraphs if they have no K t -minor for t ≤ 7. [ABSTRACT FROM AUTHOR]

Abstract We prove that every sufficiently large 6-connected graph of bounded tree-width either has a K 6 minor, or has a vertex whose deletion makes the graph planar. This is a step toward proving that the same conclusion holds for all sufficiently large 6-connected graphs. Jørgensen conjectured that it holds for all 6-connected graphs. [ABSTRACT FROM AUTHOR]

We prove that every graph with n vertices and at least 5 n − 8 edges contains the Petersen graph as a minor, and this bound is best possible. Moreover we characterise all Petersen-minor-free graphs with at least 5 n − 11 edges. It follows that every graph containing no Petersen minor is 9-colourable and has vertex arboricity at most 5. These results are also best possible. [ABSTRACT FROM AUTHOR]

A graph G is weakly 4-connected if it is 3-connected, has at least five vertices, and for every pair ( A , B ) such that A ∪ B = V ( G ) , | A ∩ B | = 3 and no edge has one end in A − B and the other in B − A , one of the induced subgraphs G [ A ] , G [ B ] has at most four edges. We describe a set of constructions that starting from a weakly 4-connected planar graph G produce a finite list of non-planar weakly 4-connected graphs, each having a minor isomorphic to G , such that every non-planar weakly 4-connected graph H that has a minor isomorphic to G has a minor isomorphic to one of the graphs in the list. Our main result is more general and applies in particular to polyhedral embeddings in any surface. [ABSTRACT FROM AUTHOR]

A graph H is a minor of a graph G if a graph isomorphic to H can be obtained from G by contracting some edges, deleting some edges, and deleting some isolated vertices. The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. One of the main aims in this work is to obtain quantitative information about the distortion of the hyperbolicity constant of the graph G/e obtained from the (simple or non-simple) graph G by contracting an arbitrary edge e from it. We prove that H is hyperbolic if and only if G is hyperbolic, for many minors H of G, even if H is obtained from G by contracting and/or deleting infinitely many edges. [ABSTRACT FROM AUTHOR]

Jørgensen conjectured that every 6-connected graph with no K 6 minor has a vertex whose deletion makes the graph planar. We prove the conjecture for all sufficiently large graphs. [ABSTRACT FROM AUTHOR]

We give an elementary and self-contained proof, and a numerical improvement, of a weaker form of the excluded clique minor theorem of Robertson and Seymour, the following. Let t , r ≥ 1 be integers, and let R = 49152 t 24 ( 40 t 2 + r ) . An r -wall is obtained from a 2 r × r -grid by deleting every odd vertical edge in every odd row and every even vertical edge in every even row, then deleting the two resulting vertices of degree one, and finally subdividing edges arbitrarily. The vertices of degree two that existed before the subdivision are called the pegs of the r -wall. Let G be a graph with no K t minor, and let W be an R -wall in G . We prove that there exist a set A ⊆ V ( G ) of size at most 12288 t 24 and an r -subwall W ′ of W such that V ( W ′ ) ∩ A = ∅ and W ′ is a flat wall in G − A in the following sense. There exists a separation ( X , Y ) of G − A such that X ∩ Y is a subset of the vertex set of the cycle C ′ that bounds the outer face of W ′ , V ( W ′ ) ⊆ Y , every peg of W ′ belongs to X and the graph G [ Y ] can almost be drawn in the unit disk with the vertices X ∩ Y drawn on the boundary of the disk in the order determined by C ′ . Here almost means that the assertion holds after repeatedly removing parts of the graph separated from X ∩ Y by a cutset Z of size at most three, and adding all edges with both ends in Z . Our proof gives rise to an algorithm that runs in polynomial time even when r and t are part of the input instance. The proof is self-contained in the sense that it uses only results whose proofs can be found in textbooks. [ABSTRACT FROM AUTHOR]

Hadwiger's conjecture from 1943 states that for every integer t ≥ 1 , every graph either can be t -colored or has a subgraph that can be contracted to the complete graph on t + 1 vertices. As pointed out by Paul Seymour in his recent survey on Hadwiger's conjecture, proving that graphs with no K 7 minor are 6-colorable is the first case of Hadwiger's conjecture that is still open. It is not known yet whether graphs with no K 7 minor are 7-colorable. Using a Kempe-chain argument along with the fact that an induced path on three vertices is dominating in a graph with independence number two, we first give a very short and computer-free proof of a recent result of Albar and Gonçalves and generalize it to the next step by showing that every graph with no K t minor is ( 2 t − 6 ) -colorable, where t ∈ { 7 , 8 , 9 } . We then prove that graphs with no K 8 − minor are 9-colorable, and graphs with no K 8 = minor are 8-colorable. Finally we prove that if Mader's bound for the extremal function for K t minors is true, then every graph with no K t minor is ( 2 t − 6 ) -colorable for all t ≥ 6 . This implies our first result. We believe that the Kempe-chain method we have developed in this paper is of independent interest. [ABSTRACT FROM AUTHOR]

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 [ABSTRACT FROM AUTHOR]

Given a graph G, the Hadwiger number of G, denoted by h(G), is the largest integer k such that G contains the complete graph Kk as a minor. A hole in G is an induced cycle of length at least four. Hadwiger's conjecture from 1943 states that for every graph G, h(G) ≥ χ(G), where χ(G) denotes the chromatic number of G. In this paper we establish more evidence for Hadwiger's conjecture by showing that if a graph G with independence number α(G) ≥ 3 has no hole of length between 4 and 2α(G) - 1, then h(G) ≥ χ(G). We also prove that if a graph G with independence number α(G) ≥ 2 has no hole of length between 4 and 2 α(G), then G contains an odd clique minor of size χ(G), that is, such a graph G satisfies the odd Hadwiger's conjecture. [ABSTRACT FROM AUTHOR]

We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an n-vertex graph embedded on a surface of genus g with at most k crossings per edge has treewidth O(√(g + 1)(k + 1)n) and layered treewidth O((g + 1)k) and t hat these bounds are tight up to a constant factor. In the special case of g = 0, so-called k-planar graphs, the treewidth bound is O(√((k + 1)n), which is tight and improves upon a known O( (k + 1)3/4n1/2) bound. Analogous results are proved for map graphs defined with respect to any surface. Finally, we show that for g < m, every m-edge graph can be embedded on a surface of genus g with O((m/(g + 1)) log² g) crossings per edge, which is tight to a polylogarithmic factor. [ABSTRACT FROM AUTHOR]

In this article, we define and study a new family of graphs that generalizes the notions of line graphs and path graphs. Let G be a graph with no loops but possibly with parallel edges. An ℓ -link of G is a walk of G of length [ABSTRACT FROM AUTHOR]

Hadwiger's conjecture asserts that every graph with chromatic number t contains a complete minor of order t. Given integers [ABSTRACT FROM AUTHOR]

A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G ( branch vertices) and edges of H are mapped to pairwise edge-disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree-like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path-like linear decomposition isolating the high degree vertices. [ABSTRACT FROM AUTHOR]