Results 161 to 170 of about 332 (184)

A Pair of Forbidden Subgraphs and 2-Factors

Combinatorics, Probability and Computing, 2012
In this paper, we consider pairs of forbidden subgraphs that imply the existence of a 2-factor in a graph. Ford≥ 2, letdbe the set of connected graphs of minimum degree at leastd. LetF1andF2be connected graphs and letbe a set of connected graphs. Then {F1,F2} is said to be a forbidden pair forif every {F1,F2}-free graph inof sufficiently large order ...
Jun Fujisawa, Akira Saito
openaire   +3 more sources

Local Density in Graphs with Forbidden Subgraphs

Combinatorics, Probability and Computing, 2003
Let \(G\) be a graph of order \(n\). It is shown for every integer \(r \geq 2\), there is a constant \(c = c(r) < 1\) such that if \(c \leq \alpha \leq 1\) and every set of \(\alpha n\) vertices span more than \((r-1)/2r(2\alpha - 1)n^2\) edges, then \(G\) contains a \(K_{r+1}\).
Peter Keevash, Benny Sudakov
openaire   +2 more sources

Forbidden Induced Subgraphs for Perfect Matchings

Graphs and Combinatorics, 2011
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Katsuhiro Ota, Gabriel Sueiro
openaire   +1 more source

Forbidden subgraphs and the existence of a 2‐factor

Journal of Graph Theory, 2009
AbstractIn this paper, we consider forbidden subgraphs which force the existence of a 2‐factor. Let \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal G}$\end{document} be the class of connected graphs of minimum degree at least two and maximum degree at least three, and let \documentclass{article}\footskip=0pc\pagestyle{empty}\
Robert E. L. Aldred, Jun Fujisawa, Akira Saito   +2 more
openaire   +1 more source

Forbidden Subgraphs of the Odd‐Distance Graph

Journal of Graph Theory, 2013
AbstractIn [2], on page 252 the following logical terminal inexactitude was made: “...the existence of a K4 is the only obstruction. That is, every finite K4‐free graph can be represented by odd‐distances in the plane.” In this note we correct this erroneous claim by showing that W5, the 5‐wheel, see Figure 1, is not a subgraph of .
Moshe Rosenfeld 0001, Nam Lê Tien
openaire   +3 more sources

A New Forbidden Subgraph for 5-Contractible Edges

Discrete Mathematics, 2020
Kiyoshi Ando
exaly  

Forbidden Pairs of Disconnected Graphs for 2-Factor of Connected Graphs

Journal of Graph Theory, 2022
Petr Vrana, Přemysl Holub, Liming Xiong
exaly  

The Forbidden Subgraph Characterization of Directed Vertex Graphs

Discrete Mathematics, 1999
B S Panda
exaly  

A Forbidden Induced Subgraph Characterization of Distance-Hereditary 5-Leaf Powers

Discrete Mathematics, 2009
Dieter Rautenbach, Andreas Brandstädt
exaly  

Automated Generation of Conjectures on Forbidden Subgraph Characterization

Discrete Applied Mathematics, 2014
Alain Hertz, Christian Desrosiers, Pierre Hansen   +2 more
exaly