Results 71 to 80 of about 9,740 (155)
Journal of Graph Theory, Volume 112, Issue 3, Page 198-208, July 2026.ABSTRACT We prove that the Ramsey number R ( 5 , 5 ) is less than or equal to 46. The proof uses a combination of linear programming and checking a large number of cases by computer. All of the computational parts of the proof were independently implemented by both authors, with consistent results.
Vigleik Angeltveit, Brendan D. McKay
wiley +1 more source
Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult [PDF]
, 2003 We consider the problem of coloring a planar graph with the minimum number of colors such that each color class avoids one or more forbidden graphs as subgraphs.
Broersma, H.J. +3 more
core +2 more sources
Towards Characterization of Five‐List‐Colorability of Toroidal Graphs
Journal of Graph Theory, Volume 112, Issue 3, Page 267-275, July 2026.ABSTRACT Through computer‐assisted enumeration, we list minimal obstructions for 5‐choosability of graphs on the torus with the following additional property: There exists a cyclic system of non‐contractible triangles around the torus where the consecutive triangles are at distance at most four.
Zdeněk Dvořák +1 more
wiley +1 more source
Forbidden Subgraphs and Complete Partitions
The Electronic Journal of CombinatoricsA graph is called an $(r,k)$-graph if its vertex set can be partitioned into $r$ parts, each having at most $k$ vertices and there is at least one edge between any two parts. Let $f(r,H)$ be the minimum $k$ for which there exists an $H$-free $(r,k)$-graph.
John Byrne, Michael Tait, Craig Timmons
openaire +2 more sources
Ramsey-type Theorems with Forbidden Subgraphs [PDF]
Combinatorica, 2001 P. Erdős and A. Hajnal conjectured that for every finite graph \(H\) every \(H\)-free graph on \(n\) vertices contains a complete or empty subgraph of size \(n^{\varepsilon(H)}\). It is shown that if the conjecture holds for \(H_1\), \(H_2\) then it holds for the graph which is \(H_1\) with one vertex blown up to a copy of \(H_2\).
Noga Alon, János Pach, József Solymosi
openaire +2 more sources
Some Variations of Perfect Graphs
Discussiones Mathematicae Graph Theory, 2016 We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively.
Dettlaff Magda +3 more
doaj +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 +3 more
doaj +1 more source
Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs
, 2016 A graph is called \emph{claw-free} if it contains no induced subgraph isomorphic to $K_{1,3}$. Matthews and Sumner proved that a 2-connected claw-free graph $G$ is hamiltonian if every vertex of it has degree at least $(|V(G)|-2)/3$. At the workshop C\&C
Li, Binlong +3 more
core +1 more source
Treewidth Versus Clique Number. V. Further Connections With Tree‐Independence Number
Journal of Graph Theory, Volume 112, Issue 3, Page 337-351, July 2026.ABSTRACT We continue the study of ( tw , ω )‐bounded graph classes, that is, hereditary graph classes in which large treewidth is witnessed by the presence of a large clique, and the relation of this property to boundedness of the tree‐independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milanič, and Štorgel ...
Claire Hilaire +2 more
wiley +1 more source
Theory and Applications of GraphsA class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by G^{apex} the class of graphs G that contain a vertex v such that G − v is in G.
Jagdeep Singh +2 more
doaj +1 more source