Search

Abstract Hadwiger's conjecture asserts that any graph contains a clique minor with order no less than the chromatic number of the graph. We prove that this well-known conjecture is true for all graphs if and only if it is true for squares of split graphs. This observation implies that Hadwiger's conjecture for squares of chordal graphs is as difficult as the general case, since chordal graphs are a superclass of split graphs. Then we consider 2-trees which are a subclass of each of planar graphs, 2-degenerate graphs and chordal graphs. We prove that Hadwiger's conjecture is true for squares of 2-trees. We achieve this by proving the following stronger result: for any 2-tree T , its square T 2 has a clique minor of order χ (T 2) for which each branch set induces a path, where χ (T 2) is the chromatic number of T 2. [ABSTRACT FROM AUTHOR]

Abstract In this paper we show that for integers s ≥ 2 , t ≥ 1 , any co-edge-regular graph which is cospectral with the s -clique extension of the t × t -grid is the s -clique extension of the t × t -grid, if t is large enough. Gavrilyuk and Koolen used a weaker version of this result to show that the Grassmann graph J q (2 D , D) is characterized by its intersection array as a distance-regular graph, if D is large enough. [ABSTRACT FROM AUTHOR]

Abstract Let G be a graph with vertex set { 1 , ... , n }. A spanning forest F of G is increasing if the sequence of labels on any path starting at the minimum vertex of a tree of F forms an increasing sequence. Hallam and Sagan showed that the generating function ISF (G , t) for increasing spanning forests of G has all nonpositive integral roots. Furthermore they proved that, up to a change of sign, this polynomial equals the chromatic polynomial of G precisely when 1 , ... , n is a perfect elimination order for G. We give new, purely combinatorial proofs of these results which permit us to generalize them in several ways. For example, we are able to bound the coefficients of ISF (G , t) using broken circuits. We are also able to extend these results to simplicial complexes using the new notion of a cage-free complex. A generalization to labeled multigraphs is also given. We observe that the definition of an increasing spanning forest can be formulated in terms of pattern avoidance, and we end by exploring spanning forests that avoid the patterns 231, 312 and 321. [ABSTRACT FROM AUTHOR]

Abstract We discuss conjectures on Hamiltonicity in cubic graphs (Tait, Barnette, Tutte), on the dichromatic number of planar oriented graphs (Neumann-Lara), and on even graphs in digraphs whose contraction is strongly connected (Hochstättler). We show that all of them fit into the same framework related to cuts in matchings. This allows us to find a counterexample to the conjecture of Hochstättler and show that the conjecture of Neumann-Lara holds for all planar graphs on at most 26 vertices. Finally, we state a new conjecture on bipartite cubic oriented graphs, that naturally arises in this setting. [ABSTRACT FROM AUTHOR]

Abstract In 1978, László Lovász proved the famous Kneser Conjecture – concerning the chromatic number of the Kneser graphs K G m , n – introducing the neighborhood complex. In the same year, Alexander Schrijver defined certain induced subgraphs of K G m , n – called the stable Kneser graphs S G m , n – and showed that they are vertex-critical. Schrijver used another, Bárány's method to obtain the chromatic number of the stable Kneser graphs. Almost 25 years later, in 2002, Anders Björner and Mark de Longueville studied the neighborhood complex of S G m , n , and determined the homotopy type of them. Frédéric Meunier generalized Schrijver's construction and formulated the conjecture on the chromatic number of the s -stable and almost s -stable Kneser graphs. We shall determine the homotopy type of the neighborhood complex of the almost s -stable Kneser graphs. In conjunction with Lovász's topological bound on the chromatic number, we give the chromatic number of these graphs, which was recently determined by Chen using other methods. [ABSTRACT FROM AUTHOR]

A graph G covers a graph H if there exists a locally bijective homomorphism from G to H . We deal with regular coverings in which this homomorphism is prescribed by an action of a semiregular subgroup Γ of Aut ( G ) ; so H ≅ G ∕ Γ . In this paper, we study the behavior of regular graph covering with respect to 1-cuts and2-cuts in G . We describe reductions which produce a series of graphs G = G 0 , … , G r such that G i + 1 is created from G i by replacing certain inclusion minimal subgraphs with colored edges. The process ends with a primitive graph G r which is either 3-connected, or a cycle, or K 2 . This reduction can be viewed as a non-trivial modification of reductions of Mac Lane (1937), Trachtenbrot (1958), Tutte (1966), Hopcroft and Tarjan (1973), Cuningham and Edmonds (1980), Walsh (1982), and others. A novel feature of our approach is that in each step all essential information about symmetries of G are preserved. A regular covering projection G 0 → H 0 induces regular covering projections G i → H i where H i is the i th quotient reduction of H 0 . This property allows to construct all possible quotients H 0 of G 0 from the possible quotients H r of G r . By applying this method to planar graphs, we give a proof of Negami’s Theorem (1988). Our structural results are also used in subsequent papers for regular covering testing when G is a planar graph and for an inductive characterization of the automorphism groups of planar graphs (see Babai (1973) as well). [ABSTRACT FROM AUTHOR]

Many famous graphs are edge-primitive. Weiss (1973) and Guo et al. (2013) determined edge-primitive graphs of valency 3 and 5, respectively. In this paper, we study edge-primitive graphs of any prime valency. It is proved that all such graphs are 2-arc-transitive and the full automorphism groups are almost simple with the only exception the graphs being the complete bipartite graphs, and a complete classification is given of such graphs with soluble edge stabilizers, which widely extends the classifications of Weiss and Guo et al. (notice that the edge stabilizers of edge-primitive graphs with valency at most 5 are soluble). [ABSTRACT FROM AUTHOR]

Let u k ( G , p ) be the maximum over all k -vertex graphs F of by how much the number of induced copies of F in G differs from its expectation in the binomial random graph with the same number of vertices as G and with edge probability p . This may be viewed as a measure of how close G is to being p -quasirandom. For a positive integer n and 0 < p < 1 , let D ( n , p ) be the distance from p n 2 to the nearest integer. Our main result is that, for fixed k ≥ 4 and for n large, the minimum of u k ( G , p ) over n -vertex graphs has order of magnitude Θ ( max { D ( n , p ) , p ( 1 − p ) } n k − 2 ) provided that p ( 1 − p ) n 1 ∕ 2 → ∞ . [ABSTRACT FROM AUTHOR]

A map is said to be even-closed if all of its automorphisms act like even permutations on the vertex set. In this paper the study of even-closed regular maps is approached by analysing two distinguished families. The first family consists of embeddings of a well-known family of graphs on distinct orientable surfaces, whereas in the second family we consider all graphs having orientable-regular embeddings on a particular surface. In particular, the classification of even-closed orientable-regular embeddings of the complete bipartite graphs K n , n and classification of even-closed orientable-regular maps on the torus are given. [ABSTRACT FROM AUTHOR]

A partition of a group is a dioid partition if the following three conditions are met: The setwise product of any two parts is a union of parts, there is a part that multiplies as an identity element, and the inverse of a part is a part. This kind of a group partition was first introduced by Tamaschke in 1968. We show that a dioid partition defines a dioid structure over the group, analogously to the way a Schur ring over a group is defined. After proving fundamental properties of dioid partitions, we focus on three part dioid partitions of cyclic groups of prime order. We provide classification results for their isomorphism types as well as for the partitions themselves. [ABSTRACT FROM AUTHOR]

The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. The Lagrangian density of an r -uniform graph F is π λ ( F ) = sup { r ! λ ( G ) : G i s F - f r e e } , where λ ( G ) is the Lagrangian of an r -uniform graph G . Recently, Lagrangian densities of hypergraphs and Turán numbers of their extensions have been studied actively. In particular, Hefetz and Keevash (2013) studied the Lagrangian density of the 3-uniform matching of size 2 and the Turán number of its extension. We obtain the Lagrangian densities of a 3-uniform matching of size t , a 3-uniform linear star of size t , and a 4-uniform linear star of size t . Using a stability argument of Pikhurko and a transference technique between the Lagrangian density of an r -uniform graph F and the Turán number of its extension, we can also determine the Turán numbers of their extensions. [ABSTRACT FROM AUTHOR]

We consider a new type of regularity we call edge-girth-regularity. An edge-girth-regular ( v , k , g , λ ) -graph Γ is a k -regular graph of order v and girth g in which every edge is contained in λ distinct g -cycles. This concept is a generalization of the well-known concept of ( v , k , λ ) -edge-regular graphs (that count the number of triangles) and appears in several related problems such as Moore graphs and Cage and Degree/Diameter Problems. All edge- and arc-transitive graphs are edge-girth-regular as well. We derive a number of basic properties of edge-girth-regular graphs, systematically consider cubic and tetravalent graphs from this class, and introduce several constructions that produce infinite families of edge-girth-regular graphs. We also exhibit several surprising connections to regular embeddings of graphs in orientable surfaces. [ABSTRACT FROM AUTHOR]

Let ⊥ be a unitary polarity of a finite projective plane π of order q 2 . The unitary polarity graph is the graph with vertex set the points of π where two vertices x and y are adjacent if x ∈ y ⊥ . We show that a triangle-free induced subgraph of the unitary polarity graph of an arbitrary projective plane has at most ( q 4 + q ) ∕ 2 vertices. When π is the Desarguesian projective plane PG ( 2 , q 2 ) and q is even, we show that the upper bound is asymptotically sharp, by providing an example on q 4 ∕ 2 vertices. Finally, the case when π is the Figueroa plane is discussed. [ABSTRACT FROM AUTHOR]

We study the dispersion of a point set, a notion closely related to the discrepancy. Given a real r ∈ ( 0 , 1 ) and an integer d ≥ 2 , let N ( r , d ) denote the minimum number of points inside the d -dimensional unit cube [ 0 , 1 ] d such that they intersect every axis-aligned box inside [ 0 , 1 ] d of volume greater than r . We prove an upper bound on N ( r , d ) , matching a lower bound of Aistleitner et al. up to a multiplicative constant depending only on r . This fully determines the rate of growth of N ( r , d ) if r ∈ ( 0 , 1 ) is fixed. [ABSTRACT FROM AUTHOR]

For two pairs of vertices x 1 , y 1 and x 2 , y 2 , Seymour and Thomassen independently presented a characterization of graphs containing no edge-disjoint ( x 1 , y 1 ) -path and ( x 2 , y 2 ) -path. In this paper we first generalize their result to k ≥ 2 pairs of vertices. Namely, for 2 k vertices x 1 , y 1 , x 2 , y 2 , … , x k , y k , we characterize the graphs without edge-disjoint ( x i , y i ) -path and ( x j , y j ) -path for any 1 ≤ i < j ≤ k . Then applying this generalization, we present a characterization of signed graphs in which there are no edge-disjoint unbalanced circuits. Finally with this characterization we further show that every flow-admissible signed graph without edge-disjoint unbalanced circuits admits a nowhere-zero 6 -flow and thus verify the well-known Bouchet’s 6 -flow conjecture for this family of signed graphs. [ABSTRACT FROM AUTHOR]

We transfer Tutte’s theory for analyzing the chromatic number of a graph using nowhere-zero-coflows and -flows (NZ-flows) to the dichromatic number of a digraph and define Neumann-Lara-flows (NL-flows). We prove that any digraph whose underlying (multi-)graph is 3 -edge-connected admits a NL-3-flow, and even a NL-2-flow in case the underlying graph is 4 -edge connected. We conjecture that 3 -edge-connectivity already guarantees the existence of a NL-2-flow, which, if true, would imply the 2-Color-Conjecture for planar graphs due to Víctor Neumann-Lara. Finally we present an extension of the theory to oriented matroids. [ABSTRACT FROM AUTHOR]

We show that every interval in the homomorphism order of finite undirected graphs is either universal or a gap. Together with density and universality this “fractal” property contributes to the spectacular properties of the homomorphism order. We first show the fractal property by using Sparse Incomparability Lemma and then by a more involved elementary argument. [ABSTRACT FROM AUTHOR]

One of the most famous algorithmic meta-theorems states that every graph property which can be defined in counting monadic second order logic (CMSOL) can be checked in linear time on graphs of bounded treewidth, which is known as Courcelle’s Theorem (Courcelle, 1990). These algorithms are constructed as finite state tree automata and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e. every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. In this paper we prove two special cases of this conjecture, first for the class of k -outerplanar graphs, which are known to have treewidth at most 3 k − 1 (Bodlaender, 1998) and for graphs of bounded treewidth without chordless cycles of length at least some constant ℓ . We furthermore show that for a proof of Courcelle’s Conjecture it is sufficient to show that all members of a graph class admit constant width tree decompositions whose bags and edges can be identified with MSOL-predicates. For graph classes that admit MSOL-definable constant width tree decompositions that have bounded degree or allow for a linear ordering of all nodes with the same parent we even give a stronger result: In that case, the counting predicates of CMSOL are not needed. [ABSTRACT FROM AUTHOR]

A harmonious coloring of a k -uniform hypergraph H is a rainbow vertex coloring such that each k -set of colors appears on at most one edge. A rainbow coloring of H is achromatic if each k -set of colors appears on at least one edge. The harmonious number (resp. achromatic number ) of H , denoted by h ( H ) (resp. ψ ( H ) ) is the minimum (resp. maximum) possible number of colors in a harmonious (resp. achromatic) coloring of H . A class H of hypergraphs is fragmentable if for every H ∈ H , H can be fragmented into components of a bounded size by removing a “small” fraction of vertices. We show that for every fragmentable class H of bounded degree hypergraphs, for every ϵ > 0 and for every hypergraph H ∈ H with m ≥ m 0 ( H , ϵ ) edges we have h ( H ) ≤ ( 1 + ϵ ) k ! m k and ψ ( H ) ≥ ( 1 − ϵ ) k ! m k . As corollaries, we answer a question posed by Blackburn concerning the maximum length of t -subset packing sequences of constant radius and derive an asymptotically tight bound on the minimum number of colors in a vertex-distinguishing edge coloring of cubic planar graphs, which is a step towards confirming a conjecture of Burris and Schelp. [ABSTRACT FROM AUTHOR]

Building upon the theory of graph limits and the Aldous–Hoover representation and inspired by Panchenko’s work on asymptotic Gibbs measures [Annals of Probability 2013], we construct continuous embeddings of discrete probability distributions. We show that the theory of graph limits induces a meaningful notion of convergence and derive a corresponding version of the Szemerédi regularity lemma. Moreover, complementing recent work Bapst et al. (2015), we apply these results to Gibbs measures induced by sparse random factor graphs and verify the “replica symmetric solution” predicted in the physics literature under the assumption of non-reconstruction. [ABSTRACT FROM AUTHOR]

Inspired by previous work of Balogh (2006), we show that, given r ≥ 5 and n large, the balanced complete bipartite graph K n ∕ 2 , n ∕ 2 is the n -vertex graph that admits the largest number of r -edge-colorings for which there is no triangle whose edges are assigned three distinct colors. Moreover, we extend this result to lower values of n when r ≥ 10 , and we provide approximate results for r ∈ { 3 , 4 } . [ABSTRACT FROM AUTHOR]

We prove that every triangle-free graph of tree-width t has chromatic number at most ⌈ ( t + 3 ) ∕ 2 ⌉ , and demonstrate that this bound is tight. The argument also establishes a connection between coloring graphs of tree-width t and on-line coloring of graphs of path-width t . [ABSTRACT FROM AUTHOR]

Kostochka and Yancey proved that every 5 -critical graph G satisfies: | E ( G ) | ≥ 9 4 | V ( G ) | − 5 4 . A construction of Ore gives an infinite family of graphs meeting this bound. We prove that there exists ϵ , δ > 0 such that if G is a 5 -critical graph, then | E ( G ) | ≥ ( 9 4 + ϵ ) | V ( G ) | − 5 4 − δ T ( G ) where T ( G ) is the maximum number of vertex-disjoint cliques of size three or four where cliques of size four have twice the weight of a clique of size three. As a corollary, a triangle-free 5 -critical graph G satisfies: | E ( G ) | ≥ ( 9 4 + ϵ ) | V ( G ) | − 5 4 . [ABSTRACT FROM AUTHOR]

A P ℓ -decomposition of a graph G is a set of pairwise edge-disjoint paths with ℓ edges that cover the edge set of G . In 1957, Kotzig proved that a 3 -regular graph admits a P 3 -decomposition if and only if it contains a perfect matching, and also asked what are the necessary and sufficient conditions for an ℓ -regular graph to admit a P ℓ -decomposition, for odd ℓ . Let g , ℓ and m be positive integers with g ≥ 3 . We prove that, (i) if ℓ is odd and m > 2 ⌊ ( ℓ − 2 ) ∕ ( g − 2 ) ⌋ , then every m ℓ -regular graph with girth at least g that contains an m -factor admits a P ℓ -decomposition; (ii) if m > ⌊ ( ℓ − 2 ) ∕ ( g − 2 ) ⌋ , then every 2 m ℓ -regular graph with girth at least g admits a P ℓ -decomposition. Furthermore, we prove that, for graphs with girth at least ℓ − 1 , statement (i) holds for every m ≥ 1 ; and observe that, statement (ii) also holds for every m ≥ 1 . [ABSTRACT FROM AUTHOR]

The generalised colouring numbers col r ( G ) and wcol r ( G ) were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have since then found important theoretical and algorithmic applications. In this paper, we dramatically improve upon the known upper bounds for generalised colouring numbers for graphs excluding a fixed minor, from the exponential bounds of Grohe et al. to a linear bound for the r -colouring number col r and a polynomial bound for the weak r -colouring number wcol r . In particular, we show that if G excludes K t as a minor, for some fixed t ≥ 4 , then col r ( G ) ≤ t − 1 2 ( 2 r + 1 ) and wcol r ( G ) ≤ r + t − 2 t − 2 ( t − 3 ) ( 2 r + 1 ) ∈ O ( r t − 1 ) . In the case of graphs G of bounded genus g , we improve the bounds to col r ( G ) ≤ ( 2 g + 3 ) ( 2 r + 1 ) (and even col r ( G ) ≤ 5 r + 1 if g = 0 , i.e. if G is planar) and wcol r ( G ) ≤ ( 2 g + r + 2 2 ) ( 2 r + 1 ) . [ABSTRACT FROM AUTHOR]

Let c be an edge-coloring of the complete n -vertex graph K n . The problem of finding properly colored and rainbow Hamilton cycles in c was initiated in 1976 by Bollobás and Erdős and has been extensively studied since then. Recently it was extended to the hypergraph setting by Dudek et al. (2012). We generalize these results, giving sufficient local (resp. global) restrictions on the colorings which guarantee a properly colored (resp. rainbow) copy of a given hypergraph G . We also study multipartite analogues of these questions. We give (up to a constant factor) optimal sufficient conditions for a coloring c of the complete balanced m -partite graph to contain a properly colored or rainbow copy of a given graph G with maximum degree Δ . Our bounds exhibit a surprising transition in the rate of growth, showing that the problem is fundamentally different in the regimes Δ ≫ m and Δ ≪ m . Our main tool is the framework of Lu and Székely for the space of random bijections, which we extend to product spaces. [ABSTRACT FROM AUTHOR]

Let ch ( G ) denote the choice number of a graph G , and let K s ∗ k be the complete k -partite graph with s vertices in each part. Erdős, Rubin, and Taylor showed that ch ( K 2 ∗ k ) = k , and suggested the problem of determining the choice number of K s ∗ k . The first author established ch ( K 3 ∗ k ) = ⌈ 4 k − 1 3 ⌉ . Here we prove ch ( K 4 ∗ k ) = ⌈ 3 k − 1 2 ⌉ . [ABSTRACT FROM AUTHOR]

Abstract The bunkbed conjecture was first posed by Kasteleyn. If G = (V , E) is a finite graph and H some subset of V , then the bunkbed of the pair (G , H) is the graph G × { 1 , 2 } plus | H | extra edges to connect for every v ∈ H the vertices (v , 1) and (v , 2). The conjecture asserts that (v , 1) is more likely to connect with (w , 1) than with (w , 2) in the independent bond percolation model for any v , w ∈ V. This is intuitive because (v , 1) is in some sense closer to (w , 1) than it is to (w , 2). The conjecture has however resisted several attempts of proof. This paper settles the conjecture in the case of a constant percolation parameter and G the complete graph. [ABSTRACT FROM AUTHOR]

A half-arc-transitive graph is a regular graph that is both vertex- and edge-transitive, but is not arc-transitive. If such a graph has finite valency, then its valency is even, and greater than 2 . In 1970, Bouwer proved that there exists a half-arc-transitive graph of every even valency greater than 2, by giving a construction for a family of graphs now known as B ( k , m , n ) , defined for every triple ( k , m , n ) of integers greater than 1 with 2 m ≡ 1 mod n . In each case, B ( k , m , n ) is a 2 k -valent vertex- and edge-transitive graph of order m n k − 1 , and Bouwer showed that B ( k , 6 , 9 ) is half-arc-transitive for all k > 1 . For almost 45 years the question of exactly which of Bouwer’s graphs are half-arc-transitive and which are arc-transitive has remained open, despite many attempts to answer it. In this paper, we use a cycle-counting argument to prove that almost all of the graphs constructed by Bouwer are half-arc-transitive. In fact, we prove that B ( k , m , n ) is arc-transitive only when n = 3 , or ( k , n ) = ( 2 , 5 ) , or ( k , m , n ) = ( 2 , 3 , 7 ) or ( 2 , 6 , 7 ) or ( 2 , 6 , 21 ) . In particular, B ( k , m , n ) is half-arc-transitive whenever m > 6 and n > 5 . This gives an easy way to prove that there are infinitely many half-arc-transitive graphs of each even valency 2 k > 2 . [ABSTRACT FROM AUTHOR]

An edge-colored graph H is called rainbow if e ( H ) = c ( H ) , where e ( H ) and c ( H ) are the number of edges of H and colors used in H , respectively. For two graphs G and H , the rainbow number r b ( G , H ) is the minimum number of colors k such that for every edge-coloring of G using k colors, G contains a rainbow H . In this paper we prove that for an edge-colored graph G on n vertices with n ≥ k ≥ 4 , if e ( G ) + c ( G ) ≥ ( n 2 ) + t n , k − 2 + 2 , then G contains a rainbow clique K k , where t n , k − 2 is the Turán number. This implies the known result r b ( K n , K k ) = t n , k − 2 + 2 , and moreover, r b ( G , K k ) ≤ e ( G ¯ ) + r b ( K n , K k ) for n ≥ k ≥ 4 . [ABSTRACT FROM AUTHOR]

Abstract: A non-increasing sequence of non-negative integers is said to be graphic if it is the degree sequence of a simple graph on vertices. Let be an (additive) Abelian group. An extremal problem for a graphic sequence to have an -connected realization is considered as follows: determine the smallest even integer such that each graphic sequence with and has an -connected realization. In this paper, we determine for . [Copyright &y& Elsevier]

Abstract: Let denote the uniformly random -regular graph on vertices. For any , we obtain estimates of the probability that the subgraph of induced by is a given graph . The estimate gives an asymptotic formula for any , provided that does not contain almost all the edges of the random graph. The result is further extended to the probability space of random graphs with a given degree sequence. [Copyright &y& Elsevier]

Abstract: Circular arc graphs are graphs whose vertices can be represented as arcs on a circle such that any two vertices are adjacent if and only if their corresponding arcs intersect. Proper circular arc graphs are graphs which have a circular arc representation where no arc is completely contained in any other arc. Hadwiger’s conjecture states that if a graph has chromatic number , then a complete graph with vertices is a minor of . We prove Hadwiger’s conjecture for proper circular arc graphs. [Copyright &y& Elsevier]

Abstract: In this paper we study a distance-regular graph of diameter such that for any given pair of vertices at distance there exists a strongly closed subgraph of diameter containing them. We prove several inequalities for intersection numbers of . We show that if the equalities hold in some of these inequalities, then is either the Odd graph, the doubled Odd graph, the doubled Grassmann graph, the Hamming graph or the dual polar graph. [Copyright &y& Elsevier]

Abstract: Let be the bipartite Ramsey number for bipartite graphs and . It is shown that the order of magnitude of is for fixed and . Moreover, if is an isolate-free bipartite graph of order having bipartition that satisfies , then can be bounded from above by for large , where and for . [Copyright &y& Elsevier]

Abstract: We consider -regular graphs with loops, and study the Lovász -numbers and Schrijver -numbers of the graphs that result when the loop edges are removed. We show that the -number dominates a recent eigenvalue upper bound on the stability number due to Godsil and Newman [C.D. Godsil and M.W. Newman. Eigenvalue bounds for independent sets, J. Combin. Theory B 98 (4) (2008) 721–734]. As an application we compute the and numbers of certain instances of Erdős–Rényi graphs. This computation exploits the graph symmetry using the methodology introduced in [E. de Klerk, D.V. Pasechnik and A. Schrijver, Reduction of symmetric semidefinite programs using the regular *-representation, Math. Program. B 109 (2–3) (2007) 613–624]. The computed values are strictly better than the Godsil–Newman eigenvalue bounds. [Copyright &y& Elsevier]

Abstract: In this paper we will determine the spectra of the local graphs of the twisted Grassmann graphs and look at its consequences for the associated Terwilliger algebras. In particular, we show that the Terwilliger algebra for the twisted Grassmann graphs does depend on the base point. More specifically, we show that for the twisted Grassmann graphs there are two vertices and such that for the Terwilliger algebra with base point all the irreducible modules are thin and for the Terwilliger algebra with base point there exist non-thin irreducible modules. [Copyright &y& Elsevier]

Abstract: Let denote a distance-regular graph with classical parameters and , . The condition on implies that is formally self-dual. For we use the adjacency matrix and dual adjacency matrix to obtain an action of the -tetrahedron algebra on the standard module of . We describe four algebra homomorphisms into from the quantum affine algebra ; using these we pull back the above -action to obtain four actions of on the standard module of . [Copyright &y& Elsevier]

Abstract: Let be an -partite -graph, all of whose sides have the same size . Suppose that there exist two sides of , each satisfying the following condition: the degree of each legal -tuple contained in the complement of this side is strictly larger than . We prove that under this condition must have a perfect matching. This answers a question of Kühn and Osthus. [Copyright &y& Elsevier]

Abstract: In 2004, Csörgő constructed a loop of nilpotency class three with abelian group of inner mappings. As of now, no other examples are known. We construct many such loops from groups of nilpotency class two by replacing the product with in certain positions, where is a central involution. The location of the replacements is ultimately governed by a symmetric trilinear alternating form. [Copyright &y& Elsevier]

Abstract: A matroid is sequential or has path width 3 if is 3-connected and its ground set has a sequential ordering, that is, an ordering such that is a 3-separation for all in . This paper proves that every sequential matroid is easily constructible from a uniform matroid of rank or corank two by a sequence of moves each of which consists of a slight modification of segment-cosegment or cosegment-segment exchange. It is also proved that if is an -element sequential matroid, then is representable over all fields with at least elements; and there is an attractive family of self-dual sequential 3-connected matroids such that is a minor of some member of this family. [Copyright &y& Elsevier]

Abstract: In 1826 N. Abel found a generalization of the binomial formula. In 1902 Abel’s theorem was further generalized by A. Hurwitz. In this paper we describe constructions that provide infinitely many identities each being a generalization of a Hurwitz’s identity. Moreover, we give combinatorial interpretations of all these identities as the forest volumes of certain directed graphs. [Copyright &y& Elsevier]

Abstract: This paper extends the widely used activation strategy of the marking game on graphs to asymmetric marking games. The extended activation strategy is then applied to asymmetric marking games on chordal graphs, -pseudo partial -trees and interval graphs. Our results improve earlier upper bounds on and , where and denote the classes of interval and chordal graphs with maximum clique size respectively. Moreover, the upper bound of is tight when is a multiple of . [Copyright &y& Elsevier]

Abstract: We show that the subconstituents of the symplectic graph are strictly Deza graphs except the trivial case when . The chromatic numbers of those subconstituents are also given. [Copyright &y& Elsevier]

Abstract: The vertex-arboricity of a graph is the minimum number of subsets into which the set of vertices of can be partitioned so that each subset induces a forest. It is well-known that for any planar graph . In this paper we prove that whenever is planar and either has no 4-cycles or any two triangles of are at distance at least 3. [Copyright &y& Elsevier]

Abstract: In 1935 Pál Erdős and György Szekeres proved that, roughly speaking, any configuration of points in general position in the plane have points in convex position — which are the vertices of a convex polygon. Later, in 1983, Bernhard Korte and László Lovász generalised this result in a purely combinatorial context; the context of greedoids. In this note we give one step further to generalise this last result for arbitrary dimensions, but in the context of separoids; thus, via the geometric representation theorem for separoids, this can be applied to families of convex bodies. Also, it is observed that the existence of some homomorphisms of separoids implies the existence of not-too-small polytopal subfamilies — where each body is separated from its relative complement. Finally, by means of a probabilistic argument, it is settled, basically, that for all , asymptotically almost all “simple” families of  “-separated” convex bodies contains a polytopal subfamily of order . [Copyright &y& Elsevier]

Abstract: We  prove a general theorem on semigroup functions that implies characterizations of graph partition functions in terms of the positive semidefiniteness (‘reflection positivity’) and rank of certain derived matrices. The theorem can be applied to undirected and directed graphs as well as hypergraphs. [Copyright &y& Elsevier]

Abstract: This paper constructs some classes of minimal circular-imperfect graphs. In particular, it is proved that there are minimal circular-imperfect graphs whose independence number and clique number are both arbitrarily large. [Copyright &y& Elsevier]

Abstract: A hypergraph is -arc transitive if its automorphism group acts transitively on the set of its -arcs. In this paper, we study -arc transitive hypergraphs. We show that if a hypergraph has degree at least three and all edges of sizes at least three, then . Besides, given an -arc transitive hypergraph, we prove that there are infinitely many -arc transitive hypergraphs that cover the given one. These results extend to hypergraph classical results by Tutte, Weiss and Biggs for graphs. [Copyright &y& Elsevier]

The problem of graphs admitting identifying codes is a recent topic. In this paper, we solve a question concerning the existence of -regular graphs admitting -identifying code. Moreover, our girth approach gives some improvements on the number of vertices of graphs which admit identifying codes. [Copyright &y& Elsevier]