Search

We call a proper edge coloring of a graph G $G$ a B‐coloring if every 4‐cycle of G $G$ is colored with four different colors. Let qB(G) ${q}_{B}(G)$ denote the smallest number of colors needed for a B‐coloring of G $G$. Motivated by earlier papers on B‐colorings, here we consider qB(G) ${q}_{B}(G)$ for planar and outerplanar graphs in terms of the maximum degree Δ=Δ(G) ${\rm{\Delta }}={\rm{\Delta }}(G)$. We prove that qB(G)≤2Δ+8 ${q}_{B}(G)\le 2{\rm{\Delta }}+8$ for planar graphs, qB(G)≤2Δ ${q}_{B}(G)\le 2{\rm{\Delta }}$ for bipartite planar graphs, and qB(G)≤Δ+1 ${q}_{B}(G)\le {\rm{\Delta }}+1$ for outerplanar graphs with Δ≥4 ${\rm{\Delta }}\ge 4$. We conjecture that, for Δ ${\rm{\Delta }}$ sufficiently large, qB(G)≤2Δ(G) ${q}_{B}(G)\le 2{\rm{\Delta }}(G)$ for planar G $G$, and qB(G)≤Δ(G) ${q}_{B}(G)\le {\rm{\Delta }}(G)$ for outerplanar G $G$. [ABSTRACT FROM AUTHOR]

How many copies of a fixed odd cycle, C2 m + 1 ${C}_{2m+1}$, can a planar graph contain? We answer this question asymptotically for m ∈{2 , 3 , 4 } $m\in \{2,3,4\}$ and prove a bound which is tight up to a factor of 3/2 for all other values of m $m$. This extends the prior results of Cox and Martin and of Lv, Győri, He, Salia, Tompkins, and Zhu on the analogous question for even cycles. Our bounds result from a reduction to the following maximum likelihood question: which probability mass μ $\mu $ on the edges of some clique maximizes the probability that m $m$ edges sampled independently from μ $\mu $ form either a cycle or a path? [ABSTRACT FROM AUTHOR]

An (r − 1, 1)-coloring of an r-regular graph G is an edge coloring (with arbitrarily many colors) such that each vertex is incident to r − 1 edges of one color and 1 edge of a different color. In this paper, we completely characterize all 4-regular pseudographs (graphs that may contain parallel edges and loops) which do not have a (3, 1)-coloring. Also, for each r ≥ 6 we construct graphs that are not (r −1, 1)-colorable and, more generally, are not (r − t, t)-colorable for small t.

We prove the endomorphism conjecture for graded posets with largest Whitney number at most 4. [ABSTRACT FROM AUTHOR]

For a planar graph H $H$, let NP(n,H) ${{\bf{N}}}_{{\mathscr{P}}}(n,H)$ denote the maximum number of copies of H $H$ in an n $n$‐vertex planar graph. In this paper, we prove that NP(n,P7)~427n4 ${{\bf{N}}}_{{\mathscr{P}}}(n,{P}_{7})\unicode{x0007E}\frac{4}{27}{n}^{4}$, NP(n,C6)~(n∕3)3 ${{\bf{N}}}_{{\mathscr{P}}}(n,{C}_{6})\unicode{x0007E}{(n\unicode{x02215}3)}^{3}$, NP(n,C8)~(n∕4)4 ${{\bf{N}}}_{{\mathscr{P}}}(n,{C}_{8})\unicode{x0007E}{(n\unicode{x02215}4)}^{4}$, and NP(n,K4{1})~(n∕6)6 ${{\bf{N}}}_{{\mathscr{P}}}(n,{K}_{4}\{1\})\,\unicode{x0007E}\,{(n\unicode{x02215}6)}^{6}$, where K4{1} ${K}_{4}\{1\}$ is the 1‐subdivision of K4 ${K}_{4}$. In addition, we obtain significantly improved upper bounds on NP(n,P2m+1) ${{\bf{N}}}_{{\mathscr{P}}}(n,{P}_{2m+1})$ and NP(n,C2m) ${{\bf{N}}}_{{\mathscr{P}}}(n,{C}_{2m})$ for m≥4 $m\ge 4$. For a wide class of graphs H $H$, the key technique developed in this paper allows us to bound NP(n,H) ${{\bf{N}}}_{{\mathscr{P}}}(n,H)$ in terms of an optimization problem over weighted graphs. [ABSTRACT FROM AUTHOR]

Given a hereditary property of graphs $\mathcal{H}$ and a $p\in [0,1]$ , the edit distance function $\textrm{ed}_{\mathcal{H}}(p)$ is asymptotically the maximum proportion of edge additions plus edge deletions applied to a graph of edge density p sufficient to ensure that the resulting graph satisfies $\mathcal{H}$. The edit distance function is directly related to other well-studied quantities such as the speed function for $\mathcal{H}$ and the $\mathcal{H}$ -chromatic number of a random graph. Let $\mathcal{H}$ be the property of forbidding an Erdős–Rényi random graph $F\sim \mathbb{G}(n_0,p_0)$ , and let $\varphi$ represent the golden ratio. In this paper, we show that if $p_0\in [1-1/\varphi,1/\varphi]$ , then a.a.s. as $n_0\to\infty$ , \begin{align*} {\textrm{ed}}_{\mathcal{H}}(p) = (1+o(1))\,\frac{2\log n_0}{n_0} \cdot\min\left\{ \frac{p}{-\log(1-p_0)}, \frac{1-p}{-\log p_0} \right\}. \end{align*} Moreover, this holds for $p\in [1/3,2/3]$ for any $p_0\in (0,1)$. A primary tool in the proof is the categorization of p-core coloured regularity graphs in the range $p\in[1-1/\varphi,1/\varphi]$. Such coloured regularity graphs must have the property that the non-grey edges form vertex-disjoint cliques. [ABSTRACT FROM AUTHOR]

Gyárfás conjectured in 2011 that every r‐edge‐colored Kn contains a monochromatic component of bounded ("perhaps three") diameter on at least n∕(r−1) vertices. Letzter proved this conjecture with diameter four. In this note we improve the result in the case of r=3: We show that in every 3‐edge‐coloring of Kn either there is a monochromatic component of diameter at most three on at least n∕2 vertices or every color class is spanning and has diameter at most four. [ABSTRACT FROM AUTHOR]

Bootstrap percolation is a deterministic cellular automaton in which vertices of a graph G begin in one of two states, "dormant" or "active." Given a fixed positive integer r, a dormant vertex becomes active if at any stage it has at least r active neighbors, and it remains active for the duration of the process. Given an initial set of active vertices A, we say that Gr‐percolates (from A) if every vertex in G becomes active after some number of steps. Let m(G,r) denote the minimum size of a set A such that Gr‐percolates from A. Bootstrap percolation has been studied in a number of settings and has applications to both statistical physics and discrete epidemiology. Here, we are concerned with degree‐based density conditions that ensure m(G,2)=2. In particular, we give an Ore‐type degree sum result that states that if a graph G satisfies σ2(G)≥n−2, then either m(G,2)=2 or G is in one of a small number of classes of exceptional graphs. (Here, σ2(G) is the minimum sum of degrees of two nonadjacent vertices in G.) We also give a Chvátal‐type degree condition: If G is a graph with degree sequence d1≤d2≤⋯≤dn such that di≥i+1 or dn−i≥n−i−1 for all 1≤i

We show that for any set S ⊆ Z with |S| = 4 there exists a 3-coloring of Z in which every translate of S receives all three colors. This implies that S has a codensity of at most 1/3, proving a conjecture of Newman. We also consider related questions in Zd, d ≥ 2. [ABSTRACT FROM AUTHOR]

A graphic sequence \pi is potentially H-graphic if there is some realization of \pi that contains H as a subgraph. The Erd\"os--Jacobson--Lehel problem asks one to determine \sigma (H, n), the minimum even integer such that any n-term graphic sequence \pi with sum at least \sigma (H, n) is potentially H-graphic. The parameter \sigma (H, n) is known as the potential function of H, and can be viewed as a degree sequence variant of the classical extremal function ex(n,H). Recently, Ferrara et al. [Combinatorica 36 (2016), pp. 687--702] determined \sigma (H, n) asymptotically for all H, which is analogous to the Erd\"os--Stone--Simonovits theorem that determines ex(n,H) asymptotically for nonbipartite H. In this paper, we investigate a stability concept for the potential number, inspired by Simonovits' classical result on the stability of the extremal function. We first define a notion of stability for the potential number that is a natural analogue to the stability given by Simonovits. However, under this definition, many families of graphs are not \sigma -stable, establishing a stark contrast between the extremal and potential functions. We then give a sufficient condition for a graph H to be stable with respect to the potential function, and characterize the stability of those graphs H that contain an induced subgraph of order \alpha (H) + 1 with exactly one edge. [ABSTRACT FROM AUTHOR]

Abstract: If G is a graph and H is a set of subgraphs of G, then an edge‐coloring of G is called H‐polychromatic if every graph from H gets all colors present in G. The H‐polychromatic number of G, denoted poly H ( G ), is the largest number of colors such that G has an H‐polychromatic coloring. In this article, poly H ( G ) is determined exactly when G is a complete graph and H is the family of all 1‐factors. In addition poly H ( G ) is found up to an additive constant term when G is a complete graph and H is the family of all 2‐factors, or the family of all Hamiltonian cycles. [ABSTRACT FROM AUTHOR]

In this paper we prove an asymptotic multipartite version of a well-known theorem of Kühn and Osthus by establishing, for any graph H with chromatic number r, the asymptotic multipartite minimum degree threshold which ensures that a large r-partite graph G admits a perfect H-tiling. We also give the threshold for an H-tiling covering all but a linear number of vertices of G, in a multipartite analogue of results of Komlós and of Shokoufandeh and Zhao. [ABSTRACT FROM AUTHOR]

The edit distance between two graphs on the same vertex set is defined to be the size of the symmetric difference of their edge sets. The edit distance function of a hereditary property [ABSTRACT FROM AUTHOR]

Two new versions of the so-called Maker-Breaker Positional Games are defined by József Beck. He defines two players, Picker and Chooser. In each round, Picker takes a pair of elements not already selected and Chooser keeps one and returns the other to Picker. In the Picker-Chooser version Picker plays as Maker and Chooser plays as Breaker, while the roles are swapped in the Chooser-Picker version. The outcome of these games is sometimes very similar to that of the traditional Maker-Breaker games. Here we show that both Picker-Chooser and Chooser-Picker games are NP-hard, which gives support to the paradigm that the games behave similarly while being quite different in definition. We also investigate the pairing strategies for Maker-Breaker games, and apply these results to the game called 'Snaky'. [ABSTRACT FROM AUTHOR]

Consider a graph G and a k-uniform hypergraph H on common vertex set [n]. We say that H is G-intersecting if for every pair of edges in X,Y∈H there are vertices x∈X and y∈Y such that x=y or x and y are joined by an edge in G. This notion was introduced by Bohman, Frieze, Ruszinko´ and Thoma who proved a natural generalization of the Erdo˝s–Ko–Rado Theorem for G-intersecting k-uniform hypergraphs for G sparse and k=O(n1/4). In this note, we extend this result to k=O(√ of n). [Copyright &y& Elsevier]