For a graph $G$ and a set $B\subseteq V(G)$, the spread $\mathrm{sp}(B)$ of $B$ is the difference between the largest and the smallest degree in $G$ of a vertex of $B$, and for an integer $k\geq 0$ the parameter $\mathrm{sp}(G,k)$ is the largest cardinality of a set $B$ with $\mathrm{sp}(B)\leq k$. Caro, Lauri and Zarb asked for the minimum of $\mathrm{sp}(G,k)$ over the maximal planar graphs of order $n$; we write $\mathrm{MP}(n,\delta ,k)$ for this minimum over the maximal planar graphs of order $n$ and minimum degree $\delta \in \{3,4,5\}$. This manuscript is intended as an exposition of the subject of spread in the degree sequence of a graph $G$, with emphasis on maximal planar graphs. We apply the general lower bound of the companion paper \cite{P1} to this class, together with further ideas, some based on Caro--West and Caro--Lauri--Zarb and some new. In particular we asymptotically determine the values of $\mathrm{MP}(n,\delta ,k)$ for every pair $(\delta ,k)$ with $\delta \in \{3,4,5\}$ and $k\geq 0$. This solution recovers the case $\mathrm{MP}(n,\delta ,0)$, which is the repetition number $\mathrm{rep}(G)$ introduced by Caro and West.
For a graph $G$ and a set $B\subseteq V(G)$, the spread $\mathrm{sp}(B)$ of $B$ is the difference between the largest and the smallest degree in $G$ of a vertex of $B$, and for an integer $k\geq0$ the parameter $\mathrm{sp}(G,k)$ is the largest cardinality of a set $B$ with $\mathrm{sp}(B)\leq k$. Caro, Lauri and Zarb...
Y. Caro, R. Škrekovski, Christina Zarb· 0 citations
A B-coloring of a graph $G$ is a proper edge-coloring in which every $4$-cycle receives four distinct colors; let $q_B(G)$ be the minimum number of colors in such a coloring. Every graph of maximum degree $\Delta$ is $K_{2,\Delta+1}$-free; hence the known $2\Delta$ bound for planar graphs with $\Delta\ge38$ (Kong et al...
For a graph $G$, we write $\mathrm{mad}(G)$ for its maximum average degree and $\mathrm{diam} G$ for its diameter. Let $R_k(G)$ be the graph whose vertices are the proper colorings of $G$ with $k$ colors, where two colorings are adjacent when they differ at one vertex. Feghali (JCTB, 2021) proved that, for fixed intege...
For a graph $H$, the suspension $\widehat H$ of $H$ is a graph obtained from $H$ by joining a new vertex to every vertex of $H$. The generalized Tur\'an number $\textrm{ex}(n,K_3,\widehat H)$ is the maximum number of triangles in an $n$-vertex $\widehat H$-free graph. For fixed $k \ge 4$, Mubayi and Mukherjee conjectur...
For a connected graph $G$, let $\tau(G)$ denote the maximum number of pairwise edge-disjoint spanning trees, and let $\rho(G)$ be its adjacency spectral radius. For integers $n\ge1$, $k\ge2$, and $k\le\delta\le2k-1$, let $\mathcal{G}_{n,\delta}$ be the class of connected $n$-vertex graphs with minimum degree $\delta$,...
For a finite graph $G$, the maximum average degree $\operatorname{mad}(G)$ is the largest average degree of a nonempty subgraph of $G$. Hendrey, Norin and Wood asked whether this parameter is partitionable, that is, whether for all positive reals $a,b$ every graph $G$ with $\operatorname{mad}(G)<a+b$ admits a vertex pa...
Andrzej Grzesik, Lenka Kopfová, Gaurav Kucheriya et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
