# Graphs and Combinatorics

Graphs and Combinatorics > 1997 > 13 > 2 > 159-165

*M*is a perfect matching in a

*k*-connected graph

*G*with independence number $$\alpha \le 1 + {3 \over 2}k$$ , then

*M*can be extended to a spanning tree of

*G*with maximum degree at most three.

Graphs and Combinatorics > 1997 > 13 > 2 > 119-137

*G*= (

*V*,

*E*) be a graph. A mapping

*f*:

*E*(

*G*) → {0, l}

^{ m }is called a

*mod*2 coding of

*G*, if the induced mapping

*g*:

*V*(

*G*) → {0, l}

^{ m }, defined as $$g(v) = \sum\limits_{u \in V,uv \in E} {f(uv)}$$ , assigns different vectors to the vertices of

*G*. Note that all summations are

*mod*2. Let

*m*(

*G*) be the smallest number

*m*for which a

*mod*2 coding of

*G*is possible. Trivially,

*m*(

*G*) ≥ ⌈Log

_{2}|

*V*|⌉. Recently,...

Graphs and Combinatorics > 1997 > 13 > 2 > 167-187

Graphs and Combinatorics > 1997 > 13 > 2 > 197-208

*m*of a family

*A*= {

*A*

_{1},...,

*A*

_{m}} of subsets of a set of

*n*elements with the property that for each

*A*

_{ i }there are at most s

*A*

_{ j }such that |

*A*

_{i}∩

*A*

_{ j }| is odd (even). A tight upper bound is given in the case

*s*<

*c*(2

^{ n,2}/

*n*). In the remaining cases we give an asymptotically tight upper bound. As an application we give a tight upper-bound for the...

Graphs and Combinatorics > 1997 > 13 > 2 > 97-118

*l*forbidden submatrices and almost all 3 ×

*l*ones. These bounds are improvements of the general bounds, or else new constructions show that the general bound is best possible. It is interesting to note that up to the...

Graphs and Combinatorics > 1997 > 13 > 2 > 139-146

*G*with each of the following properties:

*G*can be contracted to a given critical 4-chromatic graph; for each

*n*≥ 7,

*G*has

*n*vertices and three matching edges (it is also shown that such graphs must have at least $${{8n}...

Graphs and Combinatorics > 1997 > 13 > 2 > 147-158

*D*, there exists a least integer ρ

_{ c }(

*D*) =

*n*, such that every arc colouring (with an arbitrary number of colours) of the transitive tournament

*TT*

_{ n }contains a canonically coloured

*D*(in the sense of Erdös-Rado). It follows that if

*P*

_{ m }is a directed path and

*D*is an acyclic digraph, then there...

Graphs and Combinatorics > 1997 > 13 > 2 > 189-196

Graphs and Combinatorics > 1997 > 13 > 3 > 227-229

*m*≥ 3 the edges of complete graph on 2

*m*+ 1 vertices can he partitioned into

*m*2

*m*-cycles and an

*m*-cycle.

Graphs and Combinatorics > 1997 > 13 > 3 > 245-250

*G*either contains a path on

*k*vertices each of which has degree at most 5

*k*or does not contain any path on

*k*vertices; the bound 5

*k*is the best possible. Moreover, for every connected planar graph

*H*other than a path and for every integer

*m*≥ 3 there is a 3-connected planar graph

*G*such that each copy of

*H*in

*G*contains a vertex of degree at least...

Graphs and Combinatorics > 1997 > 13 > 3 > 263-266

*A*of finite graphs such that for any graph

*G*e

*A*the order |

*V*(

*k*

^{ n }(

*G*))| of the

*n*-th iterated clique graph

*k*

^{ n }(

*G*) is a linear function of

*n*. We also give examples of graphs

*G*such that |

*V*(

*k*

^{n}(

*G*))| is a polynomial of any given positive degree.

Graphs and Combinatorics > 1997 > 13 > 3 > 231-243

*n*in order as one traverses the boundary. We prove two results about the structure of this set, analogous to well-known results for Catalan triangulations of the disk. The first is a generating function for Catalan triangulations...

Graphs and Combinatorics > 1997 > 13 > 3 > 267-273

*D*= (

*V*

_{1},

*V*

_{2};

*A*) be a directed bipartite graph with |

*V*

_{1}| = |

*V*

_{2}| =

*n*≥ 2. Suppose that

*d*

_{ D }(

*x*) +

*d*

_{ D }(

*y*) ≥ 3

*n*for all

*x*∈

*V*

_{1}and

*y*∈

*V*

_{2}. Then, with one exception,

*D*contains two vertex-disjoint directed cycles of lengths 2

*n*

_{1}and 2

*n*

_{2}, respectively, for any positive integer partition

*n*=

*n*

_{1}+

*n*

_{2}. This proves a conjecture proposed in [9].

Graphs and Combinatorics > 1997 > 13 > 3 > 281-285

Graphs and Combinatorics > 1997 > 13 > 3 > 287-294

*G*,

*P*(

*G*, λ) =

*P*implies

*G*is a chordal graph. Using a previous result in [16], we give a necessary and sufficient condition for

*P*to be a chordal polynomial under the condition Σ

*m*

_{ i }=

*k*+ 3.

Graphs and Combinatorics > 1997 > 13 > 3 > 217-225

*r*,

*s*satisfying 2 ≤

*r*<

*s*there exists some

*ε*=

*ε*(

*r*,

*s*) > 0 for which we construct explicitly an infinite family of graphs

*H*

_{ r,s,n }, where

*H*

_{ r,s,n }has

*n*vertices, contains no clique on

*s*vertices and every subset of at least

*n*

^{1-ε }of its vertices contains a clique of size

*r*. The constructions are based on spectral and geometric techniques, some properties of Finite...

Graphs and Combinatorics > 1997 > 13 > 3 > 275-280

Graphs and Combinatorics > 1997 > 13 > 3 > 209-215

Graphs and Combinatorics > 1997 > 13 > 3 > 295-304