Aug 2026· Journal of Graph Theory· 2 citations· 42 references
Abstract
For a graph and a graph family , let denote the maximum number of copies of in an ‐free ‐vertex graph. Let . Bai, Tompkins, and Well conjectured that is attained if and each block of the graph is a . In this paper, we determine the exact value of and the extremal graphs for all . The novelty of our proof is to give a proper partition of the set of triangles in an extremal graph. On the basis of this partition, we obtain the partition of the edge set and thus the structure of an extremal graph. Our new method can also be applied to obtain some meaningful results in other settings.
A graph is
perfect
if, for every induced subgraph, the chromatic number equals the size of its largest clique. In 1972, Lovász established a fundamental characterization of perfect graphs, showing that a graph is perfect if and only if, for every induced subgraph, the product of the size of the largest independen...
Benjamini and Tzalik obtained an upper bound on the number of shortest paths between two vertices at distance $t$ in a multigraph of maximum degree at most $\Delta$, and proposed a conjecture on the sharp bound. In this paper, we develop a probabilistic counting argument based on probability distributions induced by ra...
Let $G$ be a finite simple graph and let $S\subseteq V(G)$. We prove that the minimum number of vertices meeting every cycle that intersects $S$ is at most the maximum number of vertices of $S$ covered by a collection of vertex-disjoint cycles. This answers a question posed by Bowler, Ghorbani, Gut, Jacobs, and Reich [...
An r-dynamic coloring of a graph G is a proper vertex coloring in which each vertex sees at least min{r, d(v)} distinct colors in its neighborhood. The minimum number of colors in such a coloring is the r-dynamic chromatic number χdr(G). We determine exact values and upper bounds of χdr for several graph classes, inclu...
Juan Gutiérrez, Grover Ugarte· Anais do XI Encontro de Teor...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
