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]

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

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]

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]