Results 71 to 80 of about 332 (184)

On Fork‐Free t‐Perfect Graphs

Journal of Graph Theory, Volume 113, Issue 4, Page 553-570, December 2026.
ABSTRACT In an effort to understand the complexity of the maximum independent set problem, Chvátal introduced t‐perfect graphs. While a full characterization of this class remains open, important progress has been made for claw‐free graphs [Bruhn and Stein, Math. Program. 2012] and P 5‐free graphs [Bruhn and Fuchs, SIAM J. Discrete Math. 2017]. We take
Yixin Cao, Shenghua Wang
wiley   +1 more source

Graph Classes Generated by Mycielskians

Discussiones Mathematicae Graph Theory, 2020
In this paper we use the classical notion of weak Mycielskian M′(G) of a graph G and the following sequence: M′0(G) = G, M′1(G) = M′(G), and M′n(G) = M′(M′n−1(G)), to show that if G is a complete graph of order p, then the above sequence is a generator ...
Borowiecki Mieczys law, Borowiecki Piotr, Drgas-Burchardt Ewa, Sidorowicz Elżbieta   +3 more
doaj   +1 more source

Characterising and recognising game-perfect graphs [PDF]

Discrete Mathematics & Theoretical Computer Science, 2019
Consider a vertex colouring game played on a simple graph with $k$ permissible colours. Two players, a maker and a breaker, take turns to colour an uncoloured vertex such that adjacent vertices receive different colours.
Dominique Andres, Edwin Lock
doaj   +1 more source

Degree Powers in Graphs with Forbidden Subgraphs [PDF]

The Electronic Journal of Combinatorics, 2004
For every real $p>0$ and simple graph $G,$ set $$ f\left( p,G\right) =\sum_{u\in V\left( G\right) }d^{p}\left( u\right) , $$ and let $\phi\left( r,p,n\right) $ be the maximum of $f\left( p,G\right) $ taken over all $K_{r+1}$-free graphs $G$ of order $n.$ We prove that, if $0 < p < r,$ then$$ \phi\left( r,p,n\right) =f\left( p,T_{r ...
Béla Bollobás, Vladimir Nikiforov 0001
openaire   +3 more sources

Chromatic Ramsey Numbers and Two‐Color Turán Densities

Journal of Graph Theory, Volume 113, Issue 4, Page 663-676, December 2026.
ABSTRACT Given a graph G, its 2‐color Turán number ex ( 2 ) ( n , G ) is the maximum number of edges in an n‐vertex graph, such that the edges can be colored with two colors avoiding a monochromatic copy of G. Let π ( 2 ) ( G ) = lim n → ∞ ex ( 2 ) ( n , G ) / n 2 be the 2‐color Turán density of G.
Maria Axenovich, Simon Gaa, Dingyuan Liu
wiley   +1 more source

Random Turán Problems for Hypergraph Expansions

Random Structures &Algorithms, Volume 69, Issue 4, December 2026.
ABSTRACT Given an r0$$ {r}_0 $$‐uniform hypergraph F$$ F $$, we define its r$$ r $$‐uniform expansion F(r)$$ {F}^{(r)} $$ to be the hypergraph obtained from F$$ F $$ by inserting r−r0$$ r-{r}_0 $$ distinct vertices into each edge of F$$ F $$, and we define ex(Gn,pr,F(r))$$ \mathrm{ex}\left({G}_{n,p}^r,{F}^{(r)}\right) $$ to be the largest F(r)$$ {F ...
Jiaxi Nie, Sam Spiro
wiley   +1 more source

Forbidden subgraphs and the König–Egerváry property

Discrete Applied Mathematics, 2013
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Flavia Bonomo, Mitre Costa Dourado, Guillermo Durán 0001, Luérbio Faria, Luciano N. Grippo, Martín Darío Safe   +5 more
openaire   +7 more sources

Lower Bounds for Maximum Weight Bisections of Weighted Triangle‐Free Subcubic Graphs

Journal of Graph Theory, Volume 113, Issue 2, Page 252-273, October 2026.
ABSTRACT A bisection of a graph is a cut in which the number of vertices in the two parts of the cut differ by at most 1. In this paper, we consider maximum weight bisections of edge‐weighted triangle‐free subcubic graphs and show that every weighted triangle‐free subcubic graph G = ( V , E , w ) Stefanie Gerke, Gregory Gutin, Anders Yeo, Yacong Zhou   +3 more
wiley   +1 more source

On the Local Resilience of Random Geometric Graphs With Respect to Connectivity and Long Cycles

Random Structures &Algorithms, Volume 69, Issue 3, October 2026.
ABSTRACT Given an increasing graph property 𝒫, a graph G$$ G $$ is α$$ \alpha $$‐resilient with respect to 𝒫 if, for every spanning subgraph H⊆G$$ H\subseteq G $$ where each vertex keeps more than a (1−α)$$ \left(1-\alpha \right) $$‐proportion of its neighbors, H$$ H $$ has property 𝒫.
Alberto Espuny Díaz, Lyuben Lichev, Alexandra Wesolek   +2 more
wiley   +1 more source

Forbidden family of Ph-magic graphs

Electronic Journal of Graph Theory and Applications
Let G be a simple, finite, and undirected graph and H be a subgraph of G. The graph G admits an H-covering if every edge in G belongs to a subgraph isomorphic to H.
Tita Khalis Maryati, Fawwaz Fakhrurrozi Hadiputra, A. N. M. Salman   +2 more
doaj   +1 more source