Nonrepetitive colorings of graphs excluding a fixed immersion or topological minor

We prove that graphs excluding a fixed immersion have bounded nonrepetitive chromatic number. More generally, we prove that if is a fixed planar graph that has a planar embedding with all the vertices with degree at least 4 on a single face, then graphs excluding as a topological minor have bounded nonrepetitive chromatic number. This is the largest class of graphs known to have bounded nonrepetitive chromatic number.     

Forbidding Kuratowski Graphs as Immersions

Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs (K₅ and K_{3, 3}) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch‐width at most 10 by repetitively applying i‐edge‐sums, for . We also use this result to give a structural characterization of graphs that exclude K_{3, 3} as an immersion.     

An Algebraic Formulation of the Graph Reconstruction Conjecture

The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck—the collection of its vertex‐deleted subgraphs. Kocay's Lemma is an important tool in graph reconstruction. Roughly speaking, given the deck of a graph G and any finite sequence of graphs, it gives a linear constraint that every reconstruction of G must satisfy. Let be the number of distinct (mutually nonisomorphic) graphs on n vertices, and let be the number of distinct decks that can be constructed from these graphs. Then the difference measures how many graphs cannot be reconstructed from their decks. In particular, the graph reconstruction conjecture is true for n‐vertex graphs if and only if . We give a framework based on Kocay's lemma to study this discrepancy. We prove that if M is a matrix of covering numbers of graphs by sequences of graphs, then . In particular, all n‐vertex graphs are reconstructible if one such matrix has rank . To complement this result, we prove that it is possible to choose a family of sequences of graphs such that the corresponding matrix M of covering numbers satisfies .     

Circumference and Pathwidth of Highly Connected Graphs

Birmele [J Graph Theory 2003] proved that every graph with circumference t has treewidth at most . Under the additional assumption of 2‐connectivity, such graphs have bounded pathwidth, which is a qualitatively stronger conclusion. Birmele's theorem was extended by Birmele et al. [Combinatorica 2007] who showed that every graph without k disjoint cycles of length at least t has treewidth . Our main result states that, under the additional assumption of ‐connectivity, such graphs have bounded pathwidth. In fact, they have pathwidth . Moreover, examples show that ‐connectivity is required for bounded pathwidth to hold. These results suggest the following general question: for which values of k and graphs H does every k‐connected H‐minor‐free graph have bounded pathwidth? We discuss this question and provide a few observations.     

Hall‐Type Results for 3‐Connected Projective Graphs

Projective planar graphs can be characterized by a set of 35 excluded minors. However, these 35 are not equally important. A set of 3‐connected members of is excludable if there are only finitely many 3‐connected nonprojective planar graphs that do not contain any graph in as a minor. In this article, we show that there are precisely two minimal excludable sets, which have sizes 19 and 20, respectively.     

Hadwiger's Conjecture for the Complements of Kneser Graphs

Hadwiger's conjecture asserts that every graph with chromatic number t contains a complete minor of order t. Given integers , the Kneser graph is the graph with vertices the k‐subsets of an n‐set such that two vertices are adjacent if and only if the corresponding k‐subsets are disjoint. We prove that Hadwiger's conjecture is true for the complements of Kneser graphs.     

Independent Set Reconfiguration in Cographs and their Generalizations

We study the following independent set reconfiguration problem, called TAR‐Reachability: given two independent sets I and J of a graph G, both of size at least k, is it possible to transform I into J by adding and removing vertices one‐by‐one, while maintaining an independent set of size at least k throughout? This problem is known to be PSPACE‐hard in general. For the case that G is a cograph on n vertices, we show that it can be solved in time , and that the length of a shortest reconfiguration sequence from I to J is bounded by (if it exists). More generally, we show that if is a graph class for which (i) TAR‐Reachability can be solved efficiently, (ii) maximum independent sets can be computed efficiently, and which satisfies a certain additional property, then the problem can be solved efficiently for any graph that can be obtained from a collection of graphs in using disjoint union and complete join operations. Chordal graphs and claw‐free graphs are given as examples of such a class .     

Forbidden Pairs of Disconnected Graphs Implying Hamiltonicity

Let H be a given graph. A graph G is said to be H‐free if G contains no induced copies of H. For a class of graphs, the graph G is ‐free if G is H‐free for every . Bedrossian characterized all the pairs of connected subgraphs such that every 2‐connected ‐free graph is hamiltonian. Faudree and Gould extended Bedrossian's result by proving the necessity part of the result based on infinite families of non‐hamiltonian graphs. In this article, we characterize all pairs of (not necessarily connected) graphs such that there exists an integer n₀ such that every 2‐connected ‐free graph of order at least n₀ is hamiltonian.     

Low Polynomial Exclusion of Planar Graph Patterns

The celebrated grid exclusion theorem states that for every h‐vertex planar graph H , there is a constant such that if a graph G does not contain H as a minor then G has treewidth at most . We are looking for patterns of H where this bound can become a low degree polynomial. We provide such bounds for the following parameterized graphs: the wheel , the double wheel , any graph of pathwidth at most 2 , and the yurt graph .     

Unitary Graphs

Unitary graphs are arc‐transitive graphs with vertices the flags of Hermitian unitals and edges defined by certain elements of the underlying finite fields. They played a significant role in a recent classification of a class of arc‐transitive graphs that admit an automorphism group acting imprimitively on the vertices. In this article, we prove that all unitary graphs are connected of diameter two and girth three. Based on this, we obtain, for any prime power , a lower bound of order on the maximum number of vertices in an arc‐transitive graph of degree and diameter two.     

Edge‐colorings avoiding rainbow stars

We consider an extremal problem motivated by a article of Balogh [J. Balogh, A remark on the number of edge colorings of graphs, European Journal of Combinatorics 27, 2006, 565–573], who considered edge‐colorings of graphs avoiding fixed subgraphs with a prescribed coloring. More precisely, given , we look for n‐vertex graphs that admit the maximum number of r‐edge‐colorings such that at most colors appear in edges incident with each vertex, that is, r‐edge‐colorings avoiding rainbow‐colored stars with t edges. For large n, we show that, with the exception of the case , the complete graph is always the unique extremal graph. We also consider generalizations of this problem.     

Finite 2‐Geodesic Transitive Graphs of Prime Valency

We classify noncomplete prime valency graphs satisfying the property that their automorphism group is transitive on both the set of arcs and the set of 2‐geodesics. We prove that either Γ is 2‐arc transitive or the valency p satisfies , and for each such prime there is a unique graph with this property: it is a nonbipartite antipodal double cover of the complete graph with automorphism group and diameter 3.     

Circuit Covers of Signed Graphs

We introduce the concept of a signed circuit cover of a signed graph. A signed circuit cover is a natural analog of a circuit cover of a graph and is equivalent to a covering of the corresponding signed graphic matroid with circuits. As in the case of graphs, a signed graph has a signed circuit cover only when it admits a nowhere‐zero integer flow. In the present article, we establish the existence of a universal coefficient such that every signed graph G that admits a nowhere‐zero integer flow has a signed circuit cover of total length at most . We show that if G is bridgeless, then , and in the general case .     

Graph Sharing Game and the Structure of Weighted Graphs with a Forbidden Subdivision

In the graph sharing game, two players share a connected graph G with nonnegative weights assigned to the vertices claiming and collecting the vertices of G one by one, while keeping the set of all claimed vertices connected through the whole game. Each player wants to maximize the total weight of the vertices they have gathered by the end of the game, when the whole G has been claimed. It is proved that for any class of graphs with an odd number of vertices and with forbidden subdivision of a fixed graph (e.g., for the class of planar graphs with an odd number of vertices), there is a constant such that the first player can secure at least the proportion of the total weight of G whenever . Known examples show that such a constant does no longer exist if any of the two conditions on the class (an odd number of vertices or a forbidden subdivision) is removed. The main ingredient in the proof is a new structural result on weighted graphs with a forbidden subdivision.     

Clique minors in double‐critical graphs

A connected t‐chromatic graph G is double‐critical if is ‐colorable for each edge . A long‐standing conjecture of Erdős and Lovász that the complete graphs are the only double‐critical t‐chromatic graphs remains open for all . Given the difficulty in settling Erdős and Lovász's conjecture and motivated by the well‐known Hadwiger's conjecture, Kawarabayashi, Pedersen, and Toft proposed a weaker conjecture that every double‐critical t‐chromatic graph contains a minor and verified their conjecture for . Albar and Gonçalves recently proved that every double‐critical 8‐chromatic graph contains a K₈ minor, and their proof is computer assisted. In this article, we prove that every double‐critical t‐chromatic graph contains a minor for all . Our proof for is shorter and computer free.     

Graph Decomposition and Parity

Motivated by a recent extension of the zero‐one law by Kolaitis and Kopparty, we study the distribution of the number of copies of a fixed disconnected graph in the random graph . We use an idea of graph decompositions to give a sufficient condition for this distribution to tend to uniform modulo q. We determine the asymptotic distribution of all fixed two‐component graphs in for all q, and we give infinite families of many‐component graphs with a uniform asymptotic distribution for all q. We also prove a negative result that no recursive proof of the simplest form exists for a uniform asymptotic distribution for arbitrary graphs.     

Cubic Graphs with Large Circumference Deficit

The circumference of a graph G is the length of a longest cycle. By exploiting our recent results on resistance of snarks, we construct infinite classes of cyclically 4‐, 5‐, and 6‐edge‐connected cubic graphs with circumference ratio bounded from above by 0.876, 0.960, and 0.990, respectively. In contrast, the dominating cycle conjecture implies that the circumference ratio of a cyclically 4‐edge‐connected cubic graph is at least 0.75. Up to our knowledge, no upper bounds on this ratio have been known before for cubic graphs with cyclic edge‐connectivity above 3. In addition, we construct snarks with large girth and large circumference deficit, solving Problem 1 proposed in [J. Hägglund and K. Markström, On stable cycles and cycle double covers of graphs with large circumference, Disc Math 312 (2012), 2540–2544].     

Decompositions of Graphs into Fans and Single Edges

Given two graphs G and H , an H‐decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H . Let be the smallest number ? such that any graph G of order n admits an H‐decomposition with at most ? parts. Pikhurko and Sousa conjectured that for and all sufficiently large n , where denotes the maximum number of edges in a graph on n vertices not containing H as a subgraph. Their conjecture has been verified by Özkahya and Person for all edge‐critical graphs H . In this article, the conjecture is verified for the k‐fan graph. The k‐fan graph , denoted by , is the graph on vertices consisting of k triangles that intersect in exactly one common vertex called the center of the k‐fan.     

Minimal Obstructions for 1‐Immersions and Hardness of 1‐Planarity Testing

A graph is 1‐planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge (and any pair of crossing edges cross only once). A non‐1‐planar graph G is minimal if the graph is 1‐planar for every edge e of G. We construct two infinite families of minimal non‐1‐planar graphs and show that for every integer , there are at least nonisomorphic minimal non‐1‐planar graphs of order n. It is also proved that testing 1‐planarity is NP‐complete.