Search

We prove that the ribbon graph polynomial of a graph embedded in an orientable surface is irreducible if and only if the embedded graph is neither the disjoint union nor the join of embedded graphs. This result is analogous to the fact that the Tutte polynomial of a graph is irreducible if and only if the graph is connected and non-separable., 15 pages - this is the authors accepted manuscript / version of record without journal provided formatting

Given a linear equation L , a set A of integers is L -free if A does not contain any non-trivial solutions to L . Meeks and Treglown (2018) showed that for certain kinds of linear equations, it is NP -complete to decide if a given set of integers contains a solution-free subset of a given size. Also, for equations involving three variables, they showed that the problem of determining the size of the largest solution-free subset is APX -hard, and that for two such equations (representing sum-free and progression-free sets), the problem of deciding if there is a solution-free subset with at least a specified proportion of the elements is also NP -complete. We answer a number of questions posed by Meeks and Treglown, by extending the results above to all linear equations, and showing that the problems remain hard for sets of integers whose elements are polynomially bounded in the size of the set. For most of these results, the integers can all be positive as long as the coefficients do not all have the same sign. We also consider the problem of counting the number of solution-free subsets of a given set, and show that this problem is #P -complete for any linear equation in at least three variables.

The mutually enriching relationship between graphs and matroids has motivated discoveries in both fields. In this paper, we exploit the similar relationship between embedded graphs and delta-matroids. There are well-known connections between geometric duals of plane graphs and duals of matroids. We obtain analogous connections for various types of duality in the literature for graphs in surfaces of higher genus and delta-matroids. Using this interplay, we establish a rough structure theorem for delta-matroids that are twists of matroids, we translate Petrie duality on ribbon graphs to loop complementation on delta-matroids, and we prove that ribbon graph polynomials, such as the Penrose polynomial, the characteristic polynomial, and the transition polynomial, are in fact delta-matroidal. We also express the Penrose polynomial as a sum of characteristic polynomials.

Let M be a matroid and e ∈ E ( M ) . The e -exchange basis graph of M has vertices labeled by bases of M , and two vertices are adjacent when the bases labeling them have symmetric difference { e , x } for some x ∈ E ( M ) . In this paper we show that a connected matroid is exactly a matroid with the property that for every element e ∈ E ( M ) , the e -exchange basis graph is connected.

We develop some basic tools to work with representable matroids of bounded tree-width and use them to prove that, for any prime power $q$ and constant $k$, the characteristic polynomial of any loopless, $GF(q)$-representable matroid with tree-width $k$ has no real zero greater than $q^{k-1}$., Comment: 16 pages

Vf-safe delta-matroids have the desirable property of behaving well under certain duality operations. Several important classes of delta-matroids are known to be vf-safe, including the class of ribbon-graphic delta-matroids, which is related to the class of ribbon graphs or embedded graphs in the same way that graphic matroids correspond to graphs. In this paper, we characterize vf-safe delta-matroids and ribbon-graphic delta-matroids by finding the minimal obstructions, called excluded 3-minors, to membership in the class. We find the unique (up to twisted duality) excluded $3$-minor within the class of set systems for the class of vf-safe delta-matroids. In the literature, binary delta-matroids appear in many different guises, with appropriate notions of minor operations equivalent to that of $3$-minors, perhaps most notably as graphs with vertex minors. We give a direct explanation of this equivalence and show that some well-known results may be expressed in terms of $3$-minors., 15 pages, 1 figure

In her paper "Generalized matroids and supermodular colourings", Tardos studied special delta-matroids obtained from sequences of Higgs lifts; these are the full Higgs lift delta-matroids that we treat and around which all of our results revolve. We give an excluded-minor characterization of the class of full Higgs lift delta-matroids within the class of all delta-matroids, and we give similar characterizations of two other minor-closed classes of delta-matroids that we define using Higgs lifts. We introduce a minor-closed, dual-closed class of Higgs lift delta-matroids that arise from lattice paths. It follows from results of Bouchet that all delta-matroids can be obtained from full Higgs lift delta-matroids by removing certain feasible sets; to address which feasible sets can be removed, we give an excluded-minor characterization of delta-matroids within the more general structure of set systems. Many of these excluded minors occur again when we characterize the delta-matroids in which the collection of feasible sets is the union of the collections of bases of matroids of different ranks, and yet again when we require those matroids to have special properties, such as being paving., 24 pages, 10 figures

We give upper and lower bounds on the number of delta-matroids, and on the number of even delta-matroids.

We prove a splitter theorem for tight multimatroids, generalizing the corresponding result for matroids, obtained independently by Brylawski and Seymour. Further corollaries give splitter theorems for delta-matroids and ribbon graphs.

J. Makowsky and B. Zilber (2004) showed that many variations of graph colorings, called CP-colorings in the sequel, give rise to graph polynomials. This is true in particular for harmonious colorings, convex colorings, mcc_t-colorings, and rainbow colorings, and many more. N. Linial (1986) showed that the chromatic polynomial $\chi(G;X)$ is #P-hard to evaluate for all but three values X=0,1,2, where evaluation is in P. This dichotomy includes evaluation at real or complex values, and has the further property that the set of points for which evaluation is in P is finite. We investigate how the complexity of evaluating univariate graph polynomials that arise from CP-colorings varies for different evaluation points. We show that for some CP-colorings (harmonious, convex) the complexity of evaluation follows a similar pattern to the chromatic polynomial. However, in other cases (proper edge colorings, mcc_t-colorings, H-free colorings) we could only obtain a dichotomy for evaluations at non-negative integer points. We also discuss some CP-colorings where we only have very partial results., Comment: 33 pages, 2 figures, 3 tables

The Merino–Welsh conjecture asserts that the number of spanning trees of a graph is no greater than the maximum of the numbers of totally cyclic orientations and acyclic orientations of that graph. We prove this conjecture for the class of series–parallel graphs.

In this paper, we study connected plane graphs with link component number equal to the nullity and call them near-extremal graphs. We first study near-extremal graphs with minimum degree at least 3 and prove that a connected plane graph G with minimum degree at least 3 is a near-extremal graph if and only if G is isomorphic to K4, the complete graph with 4 vertices. The result is obtained by studying general graphs using the knowledge of bicycle space and the Tutte polynomial. Then a simple algorithm is given to judge whether a connected plane graph is a near-extremal graph or not. Finally we study the construction of near-extremal graphs and prove that all near-extremal graphs can be constructed from a loop and K4 by two graph operations.

We consider two orientation problems in a graph, namely the minimization of the sum of all the shortest path lengths and the minimization of the diameter. We show that it is NP-complete to decide whether a graph has an orientation such that the sum of all the shortest paths lengths is at most an integer specified in the input. The proof is a short reduction from a result of Chv\'atal and Thomassen showing that it is NP-complete to decide whether a graph can be oriented so that its diameter is at most 2. In contrast, for each positive integer k, we describe a linear-time algorithm that decides for a planar graph G whether there is an orientation for which the diameter is at most k. We also extend this result from planar graphs to any minor-closed family not containing all apex graphs., Comment: 9 pages

We prove that the Tutte polynomial of a coloopless paving matroid is convex along the portions of the line segments x+y=p lying in the positive quadrant. Every coloopless paving matroids is in the class of matroids which contain two disjoint bases or whose ground set is the union of two bases of M*. For this latter class we give a proof that T_M(a,a) = 2. We conjecture that T_M(1,1), 17 pages

A mapping from the vertex set of a graph G=(V,E) into an interval of integers {0,...,k} is an L(2,1)-labelling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices at distance 2 are mapped onto distinct integers. It is known that, for any fixed k>=4, deciding the existence of such a labelling is an NP-complete problem while it is polynomial for [email protected]?3. For even k>=8, it remains NP-complete when restricted to planar graphs. In this paper, we show that it remains NP-complete for any k>=4 by reduction from Planar Cubic Two-Colourable Perfect Matching. Schaefer stated without proof that Planar Cubic Two-Colourable Perfect Matching is NP-complete. In this paper we give a proof of this.

We consider the problem of minimizing the diameter of an orientation of a planar graph. A result of Chvatal and Thomassen shows that for general graphs, it is NP- complete to decide whether a graph can be oriented so that its diameter is at most two. In contrast to this, for each constant l, we describe an algorithm that decides if a planar graph G has an orientation with diameter at most l and runs in time O(c|V |), where c depends on l.

It is known that evaluating the Tutte polynomial, T(G; x, y), of a graph, G, is nP-hard at all but eight specific points and one specific curve of the (x, y)-plane. In contrast we show that if k is a fixed constant then for graphs of tree-width at most k there is an algorithm that will evaluate the polynomial at any point using only a linear number of multiplications and additions.

We study the problem of finding the next-to-shortest paths in a graph. A next-to-shortest $(u,v)$-path is a shortest $(u,v)$-path amongst $(u,v)$-paths with length strictly greater than the length of the shortest $(u,v)$-path. In constrast to the situation in directed graphs, where the problem has been shown to be NP-hard, providing edges of length zero are allowed, we prove the somewhat surprising result that there is a polynomial time algorithm for the undirected version of the problem.

We show that for any $k$ there is a polynomial time algorithm to evaluate the weighted graph polynomial $U$ of any graph with tree-width at most $k$ at any point. For a graph with $n$ vertices, the algorithm requires $O(a_k n^{2k+3})$ arithmetical operations, where $a_k$ depends only on $k$.

The U-polynomial, the polychromate and the symmetric function generalization of the Tutte polynomial due to Stanley are known to be equivalent in the sense that the coefficients of any one of them can be obtained as a function of the coefficients of any other. The definition of each of these functions suggests a natural way in which to generalize them which also captures Tutte's universal V-functions as a specialization. We show that the equivalence remains true for the extended functions thus answering a question raised by Dominic Welsh., 17 pages

Motivated by problems in radio channel assignment, we consider the vertex-labelling of graphs with nonnegative integers. The objective is to minimize the span of the labelling, subject to constraints imposed at graph distances one and two. We show that the minimum span is (up to rounding) a piecewise linear function of the constraints, and give a complete specification, together with the associated optimal assignments, for trees and cycles.

In a recent paper Merino and Welsh (1999) studied several counting problems on the square lattice $L_n$. There the authors gave the following bounds for the asymptotics of $f(n)$, the number of forests of $L_n$, and $\alpha(n)$, the number of acyclic orientations of $L_n$: $$3.209912 \le \lim_{n\to\infty} f(n)^{1/n^2} \le 3.84161$$ and $$22/7 \le \lim_{n\to\infty} \alpha(n)^{1/n^2} \le 3.70925.$$ In this paper we improve these bounds as follows: $$3.64497 \le \lim_{n\to\infty} f(n)^{1/n^2} \le 3.74101$$ and $$3.41358 \le \lim_{n\to\infty} \alpha(n)^{1/n^2} \le 3.55449.$$ We obtain this by developing a method for computing the Tutte polynomial of the square lattice and other related graphs based on transfer matrices.

We consider the complexity of the two-variable rank generating function, $S$, of a graphic 2-polymatroid. For a graph $G$, $S$ is the generating function for the number of subsets of edges of $G$ having a particular size and incident with a particular number of vertices of $G$. We show that for any $x, y \in \mathbb{Q}$ with $xy \not =1$, it is nP-hard to evaluate $S$ at $(x,y)$. We also consider the $k$-thickening of a graph and computing $S$ for the $k$-thickening of a graph.

This is the post-print verison of the Article. The official published version can be accessed from the link below - Copyright @ 2011 Elsevier Given a graph G and a bipartition of its vertices, the edge-ratio is the minimum for both classes so defined of their number of internal edges divided by their number of cut edges. We prove that maximizing edge-ratio is NP-complete.

We give two proofs that the $h$-vector of any paving matroid is a pure O-sequence, thus answering in the affirmative a conjecture made by R. Stanley, for this particular class of matroids. We also investigate the problem of obtaining good lower bounds for the number of bases of a paving matroid given its rank and number of elements., Comment: We've corrected typos and small mistakes in the previous version. We've also tidied up a few proofs and the references

We show that the problem of recognising a partitionable simplicial complex is a member of the complexity class NP, thus answering a question raised by Kleinschmidt and Onn (1995).

We show that if G is a simple outerplanar graph and H is a graph with the same Tutte polynomial as G, then H is also outerplanar. Examples show that the condition of G being simple cannot be omitted.