Results 81 to 90 of about 332 (184)
Equivalence between Erdős–Hajnal and polynomial Rödl and Nikiforov conjectures
Bulletin of the London Mathematical Society, Volume 58, Issue 10, October 2026.Abstract It is well‐known that polynomial versions of theorems of Rödl and Nikiforov, as conjectured by Fox and Sudakov and Nguyen, Scott and Seymour imply the classical Erdős–Hajnal conjecture. In this note, we prove that these three conjectures are in fact equivalent, extending several previous particular results in this direction by Fox, Nguyen ...
Matija Bucić, Jacob Fox, Huy Tuan Pham
wiley +1 more source
Simonovits's theorem in random graphs
Proceedings of the London Mathematical Society, Volume 133, Issue 4, October 2026.Abstract Let H$H$ be a graph with χ(H)=r+1$\chi (H) = r+1$. Simonovits's theorem states that, if H$H$ is edge‐critical, the unique largest H$H$‐free subgraph of Kn$K_n$ is its largest r$r$‐partite subgraph, provided that n$n$ is sufficiently large. We show that the same holds with Kn$K_n$ replaced by the binomial random graph Gn,p$G_{n,p}$ whenever H$H$
Ilay Hoshen, Wojciech Samotij
wiley +1 more source
Eigenvalues and forbidden subgraphs I
Linear Algebra and its Applications, 2007 Some calculation errors in the first version are ...
openaire +3 more sources
Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
Discussiones Mathematicae Graph Theory, 2016 A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general.
Li Binlong +2 more
doaj +1 more source
3-Colourability and Forbidden Subgraphs
Electronic Notes in Discrete Mathematics, 2000 Abstract In this paper we investigate the chromatic aspects for graphs with forbidden induced subgraphs with emphasis on the question of 3-colourability. In the main part all possible pairs (A, B) of forbidden induced subgraphs, s.t. every A- and B -free graph is 3-colourable, are determined.
openaire +1 more source
Rainbow vertex-connection and forbidden subgraphs
Discussiones Mathematicae Graph Theory, 2018 11 ...
Li Wenjing, Li Xueliang, Zhang Jingshu
openaire +4 more sources
Local certification of forbidden subgraphs
CoRRDetecting specific structures in a network has been a very active theme of research in distributed computing for at least a decade. In this paper, we start the study of subgraph detection from the perspective of local certification. Remember that a local certification is a distributed mechanism enabling the nodes of a network to check the correctness ...
Bousquet, Nicolas +4 more
openaire +4 more sources
Line Graphs and Forbidden Induced Subgraphs
Journal of Combinatorial Theory, Series B, 2001 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Hong-Jian Lai, Lubomír Soltés
openaire +1 more source
Forbidden subgraphs and Hamiltonian properties of graphs
Discrete Mathematics, 1982 AbstractVarious sufficient conditions are given, in terms of forbidden subgraphs, that imply a graph is either homogeneously traceable, hamiltonian or pancyclic.
Ronald J. Gould, Michael S. Jacobson
openaire +3 more sources
Forbidden Subgraph Problems with Predictions
CoRRIn the Online Delayed Connected H-Node-Deletion Problem, an unweighted graph is revealed vertex by vertex and it must remain free of any induced copies of a specific connected induced forbidden subgraph H at each point in time. To achieve this, an algorithm must, upon each occurrence of H, identify and irrevocably delete one or more vertices.
Hans-Joachim Böckenhauer +3 more
openaire +2 more sources