Aug 2026· Discrete Applied Mathematics· 0 citations· 8 references
Mathematics
Abstract
For a graph $G$, let $L(G)=\max\{\omega(G),\lceil (|V(G)|+1)/(\alpha_{\min}(G)+1)\rceil\}$, where $\omega(G)$ is the clique number and $\alpha_{\min}(G)$ is the minimum, over all vertices $v$, of the largest size of an independent set containing $v$. Dybizba\'nski, Furma\'nczyk, and Mkrtchyan (Discrete Appl. Math. 354 (2024), 15--28) conjectured that every block graph $G$ satisfies $L(G)\leq\chi_{=}(G)\leq L(G)+1$, where $\chi_{=}(G)$ is the equitable chromatic number of $G$. We disprove this conjecture in a strong form. For every pair of integers $d\geq 2$ and $k\geq 4d-1$, we construct a connected block graph $G_{d,k}$ such that $L(G_{d,k})=k$ and $\chi_{=}(G_{d,k})=k+d$. Thus the difference $\chi_{=}(G)-L(G)$ is unbounded on connected block graphs.
Let $\zeta(G)$ denote the minimum number of parts in a partition of $V(G)$ in which every part induces either a clique or an independent set. Erd\H{o}s and Gimbel asked whether, for $G_n\sim G(n,1/2)$, the difference $\chi(G_n)-\zeta(G_n)$ tends to infinity with high probability. We resolve this problem along the full...
Let $G$ be a simple graph on $n$ vertices and $e(G)$ edges. Let $\mu_1\geq \cdots \geq \mu_{n-1}\geq \mu_n=0$ be the Laplacian eigenvalues of $G$. For $k=1, \ldots, n$, let $S_k(G)=\sum_{i=1}^{k}\mu_i$. Brouwers conjecture asserts that for any $k\in\{1,\ldots, n\}$, $S_k(G)\leq e(G)+\binom{k+1}{2}$. In [Bounding the su...
For a graph $G$, let $\cpn(G)$ and $\ccn(G)$ denote the minimum numbers of cliques whose edge sets partition and cover $E(G)$, respectively, and put $f(n)=\max_{|V(G)|=n}\bigl(\cpn(G)-\ccn(G)\bigr).$ In 1983, Erd\H{o}s, Faudree, and Ordman asked whether there is a sequence of graphs $G_n$ such that $|V(G_n)|=n$ and $\c...
An equitable $k$-coloring of a graph partitions its vertex set into $k$ independent sets whose sizes differ by at most one; the least such $k$ is the equitable chromatic number $\chie(G)$. Every known bound on $\chie$ valid for all graphs, beginning with the Hajnal--Szemer\'edi theorem, is linear in the maximum degree...
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
Tuza's conjecture states that for any graph $G$, the minimum size of a triangle transversal $\tau(G)$ is at most twice the maximum size of a set of edge-disjoint triangles $\nu(G)$. In this note, we prove $\tau(G) \leq \frac{63}{22}\nu(G)$, improving the previous bound $\tau(G) \leq \frac{66}{23}\nu(G)$ established by...
Lixing Yi· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
