Displaying similar documents to “Edge decompositions of graphs with no large independent sets.”

Factoring directed graphs with respect to the cardinal product in polynomial time

Wilfried Imrich, Werner Klöckl (2007)

Discussiones Mathematicae Graph Theory

Similarity:

By a result of McKenzie [4] finite directed graphs that satisfy certain connectivity and thinness conditions have the unique prime factorization property with respect to the cardinal product. We show that this property still holds under weaker connectivity and stronger thinness conditions. Furthermore, for such graphs the factorization can be determined in polynomial time.

Countable splitting graphs

Nick Haverkamp (2011)

Fundamenta Mathematicae

Similarity:

A graph is called splitting if there is a 0-1 labelling of its vertices such that for every infinite set C of natural numbers there is a sequence of labels along a 1-way infinite path in the graph whose restriction to C is not eventually constant. We characterize the countable splitting graphs as those containing a subgraph of one of three simple types.

On 1-dependent ramsey numbers for graphs

E.J. Cockayne, C.M. Mynhardt (1999)

Discussiones Mathematicae Graph Theory

Similarity:

A set X of vertices of a graph G is said to be 1-dependent if the subgraph of G induced by X has maximum degree one. The 1-dependent Ramsey number t₁(l,m) is the smallest integer n such that for any 2-edge colouring (R,B) of Kₙ, the spanning subgraph B of Kₙ has a 1-dependent set of size l or the subgraph R has a 1-dependent set of size m. The 2-edge colouring (R,B) is a t₁(l,m) Ramsey colouring of Kₙ if B (R, respectively) does not contain a 1-dependent set of size l (m, respectively);...