Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Ron Aharoni, Eli Berger, Dani Kotlar, Ran Ziv For a simplicial complex C denote by β ( C ) the minimal number of edges from C needed to cover the ground set. If C is a matroid then for every partition A 1 , … , A m of the ground set there exists a set S ∈ C meeting each A i in at least A i β ( C ) elements. We conjecture a slightly weaker statement for the intersection of two matroids: if D = P ∩ Q , where P , Q are matroids on the same ground set V, and β ( P ) , β ( Q ) ≤ k , then for every partition A 1 , … , A m of the ground set there exists a set S ∈ D meeting each A i in at least 1 k A i − 1 elements. We prove that when m = 2 there is a set meeting each A i in at least ( 1 k − 1 V ) A i − 1 elements.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Elad Aigner-Horev, David Conlon, Hiệp Hàn, Yury Person, Mathias Schacht A graph G is called quasirandom if it possesses typical properties of the corresponding random graph G ( n , p ) with the same edge density as G. A well-known theorem of Chung, Graham and Wilson states that, in fact, many such ‘typical’ properties are asymptotically equivalent and, thus, a graph G possessing one property immediately satisfies the others. In recent years, more quasirandom graph properties have been found and extensions to hypergraphs have been explored. For the latter, however, there exist several distinct notions of quasirandomness. A complete description of these notions has been provided recently by Towsner, who proved several central equivalences using an analytic framework. The purpose of this paper is to give short purely combinatorial proofs of most of Towsner's results.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Elad Aigner-Horev, Hiệp Hàn We establish an equivalence between the two seemingly distant notions of quasi-randomness: small linear bias of subsets of abelian groups and uniform edge distribution for uniform hypergraphs. For a subset A ⊂ G of an abelian group G consider the k-uniform Cayley (sum) hypergraph H ( k ) ( A ) . The vertex set of H ( k ) A is G and the edges are k-element sets { x 1 , … , x k } ∈ ( G k ) with x 1 + … + x k ∈ A . For d ∈ ( 0 , 1 ) we show that sets A ⊂ G of density d + o ( 1 ) have all non-trivial Fourier coefficients of order o ( G ) if and only if e ( U ) = d ( U k ) + o ( G k ) for all U ⊂ V ( H ( k ) ( A ) ) . This connects the work of Chung and Graham on quasi-random subsets of the integers and that of Conlon-Hàn-Person-Schacht on weak/linear quasi-random hypergraphs. Further, it extends the work of Chung and Graham who established the corresponding result for k = 2 and G = Z n .

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Margarita Akhmejanova, Dmitry Shabanov The paper deals with an extremal problem concerning colorings of hypergraphs with bounded edge degrees. Consider the family of b-simple hypergraphs, in which any two edges do not share more than b common vertices. We prove that for n ≥ n 0 ( b ) , any n-uniform b-simple hypergraph with the maximum edge degree at most c n r n − b is r-colorable, where c > 0 is an absolute constant.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Peter Allen, Julia Böttcher, Jan Hladký, Diana Piguet We prove that if G is a family of graphs with at most n vertices each, with constant degeneracy, with maximum degree at most O ( n / log n ) , and with total number of edges at most ( 1 − o ( 1 ) ) ( n 2 ) , then G packs into the complete graph K n .

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Andrés Aranda, David Bradley-Williams, Eng Keat Hng, Jan Hubička, Miltiadis Karamanlis, Michael Kompatscher, Matěj Konečný, Micheal Pawliuk We prove that certain classes of metrically homogeneous graphs omitting triangles of odd short perimeter as well as triangles of long perimeter have the extension property for partial automorphisms and we describe their Ramsey expansions.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Andrei Asinowski, Gill Barequet, Yufei Zheng A polyomino is an edge-connected set of cells on Z 2 . To-date, no formulae enumerating polyominoes by area (number of cells) or perimeter (number of empty cells neighboring the polyomino) are known. We present a few formulae enumerating polyominoes with a fixed deviation from the maximum possible perimeter.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Jasine Babu, Manu Basavaraju, L. Sunil Chandran, Mathew C. Francis Given a graph G = ( V , E ) whose vertices have been properly coloured, we say that a path in G is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy Theorem that every properly coloured graph contains a colourful path on χ ( G ) vertices. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on χ ( G ) vertices and prove its correctness when the girth of G is at least χ ( G ) . Recent work on this conjecture by Gyárfás and Sárközy, and Scott and Seymour has shown the existence of a function f such that if χ ( G ) ≥ f ( k ) , then an induced colourful path on k vertices is guaranteed to exist in any properly coloured triangle-free graph G.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Martin Balko, Jan Kynčl, Stefan Langerman, Alexander Pilz Let A and B be two finite sets of points in the plane in general position (neither of these sets contains three collinear points). We say that A lies deep below B if every point from A lies below every line determined by two points from B and every point from B lies above every line determined by two points from A. A point set P is decomposable if either P = 1 or there is a partition P 1 ∪ P 2 of P into nonempty and decomposable sets such that P 1 is to the left of P 2 and P 1 is deep below P 2. Extending a result of Nešetřil and Valtr, we show that for every decomposable point set Q and a positive integer k there is a finite set P of points in the plane in general position that satisfies the following Ramsey-type statement. For any partition C 1 ∪ ⋯ ∪ C k of the pairs of points from P (that is, of the edges of the complete graph on P), there is a subset Q ′ of P with the same triple-orientations as Q such that all pairs of points from Q ′ are in the same part C i . We then use this result to show that for every k there is a point set P such that no function Γ that maps ordered pairs of distinct points from P to a set of size k can satisfy the following property: if Γ attains the same values on two ordered triples of points from P, then these triples have the same orientation. Intuitively, this implies that there cannot be such a function that is defined locally and determines the orientation of point triples.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Igor Balla, Felix Dräxler, Peter Keevash, Benny Sudakov A family of lines through the origin in a Euclidean space is called equiangular if any pair of lines defines the same angle. The problem of estimating the maximum cardinality of such a family in R n was studied extensively for the last 70 years. Motivated by a question of Lemmens and Seidel from 1973, we prove that for every fixed angle θ and n sufficiently large, there are at most 2 n − 2 lines in R n with common angle θ. Moreover, this is achievable only for θ = arccos 1 3 . We also study analogous questions for k-dimensional subspaces. We discuss natural ways of defining the angle between k-dimensional subspaces and correspondingly study the maximum size of an equiangular set of k-dimensional subspaces in R n , obtaining bounds which extend and improve a result of Blokhuis.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Afonso S. Bandeira, Asaf Ferber, Matthew Kwan Consider the sum X ( ξ ) = ∑ i = 1 n a i ξ i , where a = ( a i ) i = 1 n is a sequence of non-zero reals and ξ = ( ξ i ) i = 1 n is a sequence of i.i.d. Rademacher random variables (that is, Pr [ ξ i = 1 ] = Pr [ ξ i = − 1 ] = 1 / 2 ). The classical Littlewood-Offord problem asks for the best possible upper bound on the concentration probabilities Pr [ X = x ] . We study a resilience version of the Littlewood-Offord problem: how many of the ξ i is an adversary typically allowed to change without being able to force concentration on a particular value' We solve this problem asymptotically, demonstrating an interesting connection to the notion of an additive basis from additive combinatorics. We also present several interesting open problems.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): J. de O. Bastos, G.O. Mota, M. Schacht, J. Schnitzer, F. Schulenburg We prove for all k ≥ 4 and 1 ≤ ℓ < k / 2 the sharp minimum ( k − 2 )-degree bound for a k-uniform hypergraph H on n vertices to contain a Hamiltonian ℓ-cycle if k − ℓ divides n and n is sufficiently large. This extends a result of Han and Zhao for 3-uniform hypergraphs.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Stéphane Bessy, Jocelyn Thiebaut Let D be a k-regular bipartite tournament. We show that, for every even p with 4 ≤ p ≤ V ( D ) − 4 , D has a cycle C of size p such that D \ C is Hamiltonian unless D is isomorphic to a special digraph, F 4 k . This result proves a conjecture of Manoussakis, Song and Zhang.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): David Bevan, Robert Brignall, Andrew Elvey Price, Jay Pantone We establish a lower bound of 10.271 for the growth rate of the permutations avoiding 1324, and an upper bound of 13.5. This is done by first finding the precise growth rate of a subclass whose enumeration is related to West-2-stack-sortable permutations, and then combining copies of this subclass in particular ways.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Vladimir Bondarenko, Andrei Nikolaev We consider the skeleton of the pyramidal tours polytope PYR(n) that is defined as the convex hull of characteristic vectors of all pyramidal tours in the complete graph K n . We describe necessary and sufficient condition for the adjacency of vertices of PYR(n) polytope. Based on that, we establish that the diameter of PYR(n) skeleton equals 2, and the asymptotically exact estimate of PYR(n) skeleton's clique number is Θ ( n 2 ) . This value characterizes the time complexity in a broad class of algorithms based on linear comparisons.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Marthe Bonamy, Kitty Meeks We introduce a variant of the well-studied sum choice number of graphs, which we call the interactive sum choice number. In this variant, we request colours to be added to the vertices' colour-lists one at a time, and so we are able to make use of information about the colours assigned so far to determine our future choices. The interactive sum choice number cannot exceed the sum choice number and we conjecture that, except in the case of complete graphs, the interactive sum choice number is always strictly smaller than the sum choice number. In this paper we provide evidence in support of this conjecture, demonstrating that it holds for a number of graph classes, and indeed that in many cases the difference between the two quantities grows as a linear function of the number of vertices.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Fábio Botler, Alexandre Talon A P ℓ -decomposition of a graph G is a set of edge-disjoint copies of P ℓ in G that cover the edge set of G, where P ℓ is the path with ℓ edges. Kouider and Lonc [M. Kouider, Z. Lonc, Path decompositions and perfect path double covers, Australas. J. Combin. 19 (1999) 261–274] conjectured that any 2ℓ-regular graph G admits a P ℓ -decomposition D where every vertex of G is the end-vertex of exactly two paths of D. In this paper we verify Kouider and Lonc's Conjecture for paths of length 4.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Julia Böttcher, Richard Montgomery, Olaf Parczyk, Yury Person We study the model of randomly perturbed dense graphs, which is the union of any graph G α with minimum degree αn and the binomial random graph G ( n , p ) . For p = ω ( n − 2 / ( Δ + 1 ) ) , we show that G α ∪ G ( n , p ) contains any single spanning graph with maximum degree Δ. As in previous results concerning this model, the bound for p we use is lower by a log-term in comparison to the bound known to be needed to find the same subgraph in G ( n , p ) alone.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Henning Bruhn, Matthias Heinlein A family F of graphs has the edge-Erdős-Pósa property if there is a function f : N → N such that for every k ∈ N and every graph G, the following holds: either G contains k edge-disjoint subgraphs contained in F or there is an edge set Y of size at most f(k) such that G − Y does not contain any subgraph in F . We prove that the family of graphs that have K 4 as a minor has the edge-Erdős-Pósa property.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Matija Bucić, Shoham Letzter, Benny Sudakov Given an oriented graph H, the k-colour oriented Ramsey number of H, denoted by r → ( H , k ) , is the least integer n, for which every k-edge-coloured tournament on n vertices contains a monochromatic copy of H. We show that r → ( T , k ) ≤ c k T k for any oriented tree T, which, in general, is tight up to a constant factor. We also obtain a stronger bound, when H is an arbitrarily oriented path.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Matija Bucić, Shoham Letzter, Benny Sudakov We prove that, with high probability, any 2-edge colouring of a random tournament on n vertices contains a monochromatic path of length Ω ( n / log n ) . This resolves a conjecture of Ben-Eliezer, Krivelevich and Sudakov and implies a nearly tight upper bound on the oriented size Ramsey number of a directed path.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Sebastián Bustamante, Hiệp Hàn, Maya Stein We show that any 2-colouring of the 3-uniform complete hypergraph K n ( 3 ) on n vertices contains two disjoint monochromatic tight cycles of distinct colours covering all but o(n) vertices of K n ( 3 ) . The same result holds if we replace tight cycles with loose cycles.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Wouter Cames van Batenburg, Ross J. Kang Two graphs G 1 and G 2 on n vertices are said to pack if there exist injective mappings of their vertex sets into [n] such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollobás and Eldridge and, independently, Catlin, asserts that, if ( Δ ( G 1 ) + 1 ) ( Δ ( G 2 ) + 1 ) ≤ n + 1 , then G 1 and G 2 pack. We consider the validity of this assertion under the additional assumptions that neither G 1 nor G 2 contain a 4-, 6- or 8-cycle, and that Δ ( G 1 ) or Δ ( G 2 ) is large enough (≥940060).

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Pilar Cano, Guillem Perarnau, Oriol Serra We study the existence of rainbow perfect matching and rainbow Hamiltonian cycles in edge–colored graphs where every color appears a bounded number of times. We derive asymptotically tight bounds on the minimum degree of the host graph for the existence of such rainbow spanning structures. The proof uses a probabilisitic argument combined with switching techniques.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, Josef Schicho Laman graphs model planar frameworks which are rigid for a general choice of distances between the vertices. There are finitely many ways, up to isometries, to realize a Laman graph in the plane. In a recent paper we provide a recursion formula for this number of realizations using ideas from algebraic and tropical geometry. Here, we present a concise summary of this result focusing on the main ideas and the combinatorial point of view.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Cesar Ceballos, Arnau Padrol, Camilo Sarmiento We show that the ν-Tamari lattices of Préville-Ratelle and Viennot can obtained as the duals of certain subword complexes. This generalizes a known result for the classical Tamari lattice, provides a simple description of the lattice property using certain bracket vectors of ν-trees, and gives (conjectural) insight on the geometry of more general objects in terms of polytopal subdivisions of multiassociahedra.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Steven Chaplick, Peter Zeman Biró, Hujter, and Tuza introduced the concept of H-graphs (1992), intersection graphs of connected subgraphs of a subdivision of a fixed graph H. They naturally generalize many important classes of graphs. We continue their study by considering coloring, clique, and isomorphism problems. We show that if H contains a certain multigraph as a minor, then H-graphs are GI-complete and the clique problem is APX-hard. Also, when H is a cactus the clique problem can be solved in polynomial time and when a graph G has a Helly H-representation, the clique problem can be solved in polynomial time. We use treewidth to show that both the k-clique and list k-coloring problems are FPT on H-graphs. These results also apply to treewidth-bounded classes where treewidth is bounded by a function of the clique number.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Herman Z.Q. Chen, Sergey Kitaev, Torsten Mütze, Brian Y. Sun A universal word for a finite alphabet A and some integer n ≥ 1 is a word over A such that every word of length n appears exactly once as a (consecutive) subword. It is well-known and easy to prove that universal words exist for any A and n. In this work we initiate the systematic study of universal partial words. These are words that in addition to the letters from A may contain an arbitrary number of occurrences of a special ‘joker’ symbol ⋄ ∉ A , which can be substituted by any symbol from A. For example, u = 0 ⋄ 011100 is a universal partial word for the binary alphabet A = { 0 , 1 } and for n = 3 (e.g., the first three letters of u yield the subwords 000 and 010). We present results on the existence and non-existence of universal partial words in different situations (depending on the number of ⋄s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Shuya Chiba For a vertex subset X of a graph G, let Δ 2 ( X ) be the maximum degree sum of two distinct vertices of X. In this paper, we give the following result: Let k be a positive integer, and let G be an m-connected graph of order n ≥ 5 k − 2 . If Δ 2 ( X ) ≥ n for every independent set X of size ⌈ m / k ⌉ + 1 in G, then G has a 2-factor with exactly k cycles. This is a common generalization of the results obtained by Brandt et al. [Degree conditions for 2-factors, J. Graph Theory 24 (1997), 165–173] and Yamashita [On degree sum conditions for long cycles and cycles through specified vertices, Discrete Math. 308 (2008), 6584–6587], respectively.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Hojin Choi, O-joung Kwon, Sang-il Oum, Paul Wollan A class of graphs is χ-bounded if there exists a function f : N → N such that for every graph G in the class and an induced subgraph H of G, if H has no clique of size q + 1 , then the chromatic number of H is less than or equal to f(q). We denote by W n the wheel graph on n + 1 vertices. We show that the class of graphs having no vertex-minor isomorphic to W n is χ-bounded. This generalizes several previous results; χ-boundedness for circle graphs, for graphs having no W 5 vertex-minors, and for graphs having no fan vertex-minors.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): M. Collares, Y. Kohayakawa, R. Morris, G.O. Mota We study the number of orientations T r ( n , p ) of the binomial random graph G ( n , p ) in which every copy of K r is transitive. We give the correct order of growth of log 2 T r ( n , p ) up to polylogarithmic factors. In particular, this significantly improves a result of Allen, Kohayakawa, Mota and Parente on T 3 ( n , p ) .

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Lucas de Oliveira Contiero, Carlos Hoppen, Hanno Lefmann, Knut Odermann We obtain sharper stability results for hypergraphs that avoid a copy of an expanded complete 2-graph and for hypergraphs that avoid a Fan subhypergraph. We apply this to an edge-coloring problem on uniform hypergraphs, where we wish to find an n-vertex hypergraph with the largest number of colorings avoiding a rainbow copy of a fixed hypergraph F.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Gwendal Collet, Élie de Panafieu, Danièle Gardy, Bernhard Gittenberger, Vlady Ravelomanana We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, including the case of constrained degrees. Our approach relies heavily on analytic combinatorics and on the notion of patchwork to describe the possible overlapping of copies.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Oliver Cooley, Penny Haxell, Mihyun Kang, Philipp Sprüssel We consider simplicial complexes that are generated from the binomial random 3-uniform hypergraph by taking the downward-closure. We determine when this simplicial complex is homologically connected, meaning that its first homology group with coefficients in F2 vanishes and the zero-th homology group is isomorphic to F2. Although this is not intrinsically a monotone property, we show that it has a single sharp threshold, and indeed prove a hitting time result relating the connectedness to the disappearance of the last minimal obstruction.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Jan Corsten The grid Ramsey number G(r) is the smallest number n such that every edgecolouring of the grid graph Γ n , n : = K n × K n with r colours induces a rectangle whose parallel edges receive the same colour. We show G ( r ) ≤ r ( r + 1 2 ) − ( 1 / 4 − o ( 1 ) ) r ( r 2 ) + 1 slightly improving the currently best known upper bound due to Gyárfás.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): David Coudert, Guillaume Ducoffe We answer open questions of [Verbeek and Suri, SOCG'14] on the relationships between Gromov hyperbolicity and the optimal stretch of graph embeddings in Hyperbolic space. Then, based on the relationships between hyperbolicity and Cops and Robber games, we turn necessary conditions for a graph to be Cop-win into sufficient conditions for a graph to have a large hyperbolicity (and so, no low-stretch embedding in Hyperbolic space). In doing so we derive lower-bounds on the hyperbolicity in various graph classes – such as Cayley graphs, distance-regular graphs and generalized polygons, to name a few. It partly fills in a gap in the literature on Gromov hyperbolicity, for which few lower-bound techniques are known.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Konrad K. Dabrowski, Daniël Paulusma Testing if a given graph G contains the k-vertex path P k as a minor or as an induced minor is trivial for every fixed integer k ≥ 1 . The situation changes for the problem of checking if a graph can be modified into P k by using only edge contractions. In this case the problem is known to be NP-complete even if k = 4 . This led to an intensive investigation for testing contractibility on restricted graph classes. We focus on bipartite graphs. Heggernes, van 't Hof, Lévêque and Paul proved that the problem stays NP-complete for bipartite graphs if k = 6 . We strengthen their result from k = 6 to k = 5 . We also show that the problem of contracting a bipartite graph to the 6-vertex cycle C 6 is NP-complete. The cyclicity of a graph is the length of the longest cycle the graph can be contracted to. As a consequence of our second result, determining the cyclicity of a bipartite graph is NP-hard.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Ewan Davies, Matthew Jenssen, Barnaby Roberts, Will Perkins We show how to use the recently-developed occupancy method and stability results that follow easily from the method to obtain extremal bounds on the individual coefficients of the partition functions over various classes of bounded degree graphs. As applications, we prove new bounds on the number of independent sets and matchings of a given size in regular graphs. For large enough graphs and almost all sizes, the bounds are tight and confirm the Upper Matching Conjecture of Friedland, Krop, and Markström, and a conjecture of Kahn on independent sets for a wide range of parameters. Additionally we prove tight bounds on the number of q-colorings of cubic graphs with a given number of monochromatic edges, and tight bounds on the number of independent sets of a given size in cubic graphs of girth at least 5.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Anuj Dawar, Simone Severini, Octavio Zapata Two graphs are cospectral if their respective adjacency matrices have the same multiset of eigenvalues. Cospectrality is an equivalence relation on graphs with many interesting facets. Isomorphic graphs are necessarily cospectral but the converse is not always true, thus cospectrality is a coarser relation than graph isomorphism. Here we study cospectrality from the point of view of pebble games, which are certain type of combinatorial games used in Finite Model Theory to capture the notion of elementary equivalence induced by various logic.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Michal Dębski, Jarosław Grytczuk, Urszula Pastwa, Barbara Pilat, Joanna Sokół, Michał Tuczyński, Przemysław Wenus, Krzysztof Węsek We say that a coloring of R 2 is line k-nonrepetitive if we will never encounter the same sequence of colors k times in a row when going along any straight line with steps of length 1 unit. This notion is closely related to square- and cube-free words, introduced by Thue. We show that there exists a line 40-nonrepetitive coloring of the plane with only 2 colors. Moreover, we generalize this result for higher dimensions and more general patterns. It complements recent results concerning line 2-nonrepetitive colorings of the plane.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Michelle Delcourt, Luke Postle Barát and Thomassen Conjectured in 2006 that the edges of every planar 4-regular 4-edge-connected graph can be decomposed into copies of the star with 3 leaves. Shortly afterward, Lai constructed a counterexample to this conjecture. Using the small subgraph conditioning method of Robinson and Wormald, we prove that a random 4-regular graph has an S 3-decomposition asymptotically almost surely, provided that the number of vertices is divisible by 3.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Michelle Delcourt, Luke Postle The chromatic number of a graph is bounded below by its clique number and from above by its maximum degree plus one. In 1998, Reed conjectured that the chromatic number is at most halfway in between these trivial lower and upper bounds. Moreover, Reed proved that its at most some non-trivial convex combination of the two bounds. In 2012, King and Reed produced a short proof that, provided the maximum degree is large enough, a combination of 1/130,000 suffices. Recently Bonamy, Perrett, and the second author improved this to 1/26. It is natural to wonder if similar results hold for the list chromatic number. Unfortunately, previous techniques for ordinary coloring do not extend to list coloring. In this paper, we overcome these hurdles by introducing several new ideas. Our main result is that the list chromatic number is at most some non-trivial convex combination of the clique number and the maximum degree plus one. Furthermore, we show that for large enough maximum degree, that a combination of 1/13 suffices. Note that this also improves on the best known results for ordinary coloring.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Ajit A. Diwan, Bodhayan Roy, Subir Kumar Ghosh We give a polynomial-time algorithm to decide whether a connected bipartite graph admits a two-layer drawing in the plane such that a specified subset of pairs of disjoint edges cross. We consider the problem of deciding whether there exists such a drawing in which a specified subset of triples of pairwise crossing edges are concurrent. We give a necessary condition for the same and conjecture that it is sufficient.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Martin Doležal, Jan Hladký, Ping Hu, Diana Piguet Much of discrete optimization concerns problems whose underlying structures are graphs. Here, we translate the theory around the maximum matching problem to the setting of graphons. We study continuity properties of the thus defined matching ratio, limit versions of matching polytopes and vertex cover polytopes, and deduce a version of the LP duality for the problem of maximum fractional matching in the graphon setting.

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Chris Dowden, Mihyun Kang, Philipp Sprüssel For integers g , m ≥ 0 and n > 0 , let S g ( n , m ) denote the graph taken uniformly at random from the set of all graphs on { 1 , 2 , … , n } with exactly m = m ( n ) edges and with genus at most g. We use counting arguments to investigate the components, subgraphs, maximum degree, and largest face size of S g ( n , m ) , finding that there is often different asymptotic behaviour depending on the ratio m n .

Abstract: Publication date: August 2017 Source:Electronic Notes in Discrete Mathematics, Volume 61 Author(s): Zdeněk Dvořák, Bojan Mohar, Robert Šámal We prove that, in several settings, a graph has exponentially many nowhere-zero flows. Our results may be seen as a counting alternative to the well-known proofs of existence of Z 3 -, Z 4 -, and Z 6 -flows. In the dual setting, proving exponential number of 3-colorings of planar triangle-free graphs is a related open question due to Thomassen.