Aug 2026· Journal of Graph Theory· 0 citations· 7 references
Abstract
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 independent set and the size of the largest clique is at least the number of vertices. His proof relied on the technique of vertex replication. In this paper, we present an alternative proof of Lovász's result that avoids vertex replication. As vertex replication does not in general preserve ‐perfection, the argument developed here applies to the study of ‐perfect graphs, a class introduced by Ravindra in 2011.
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...
Xiaojun Zhao, Yuejian Peng· Journal of Graph Theory· 2 citations
A set S of vertices of a graph is odd independent if it is independent and every vertex outside S has either zero or an odd number of neighbors in S. The largest size of such a set is the odd independence number alpha_od. Caro, Petrusevski, Skrekovski and Tuza [2] conjectured that alpha_od = 1 for every finite Queen gr...
M. Knor, Jelena Sedlar, R. Škrekovski· 0 citations
Let G be a nonempty finite simple graph of order n, and let m(G) be the upper median of its degree sequence. We prove that the 2-domination number satisfies gamma_2(G)<= n - m(G) + 1. This proves Graffiti.pc Conjecture 387. In fact, the argument establishes the inequality for every nonempty finite simple graph, so the...
Sharma and Panda recently proved that every bipartite graph with a perfect matching has property (P); that is, it admits a non-singular real symmetric matrix with support graph G for which every vertex is a P -vertex. In this paper, we extend their result from bipartite graphs to arbitrary graphs. To this end, we intro...
The chromatic threshold, originating in a question of Erd\H{o}s and Simonovits, asks when a linear minimum-degree condition forces bounded chromatic number in H-free graphs. Motivated by a question of Thomassen, the homomorphism threshold asks for the stronger conclusion that every such graph admits a homomorphism to a...
Xin-Qi Huang, Mingyuan Rong, C. Shangguan· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
