# Vol. 13 no. 2

### 1. An expected polynomial time algorithm for coloring 2-colorable 3-graphs

We present an algorithm that for 2-colorable 3-uniform hypergraphs, finds a 2-coloring in average running time O (n(5) log(2) n).
Section: Graph and Algorithms

### 2. Parameterized Problems Related to Seidel's Switching

Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. […]
Section: Graph and Algorithms

### 3. Random 2-SAT Solution Components and a Fitness Landscape

We describe a limiting distribution for the number of connected components in the subgraph of the discrete cube induced by the satisfying assignments to a random 2-SAT formula. We show that, for the probability range where formulas are likely to be satisfied, the random number of components […]
Section: Graph and Algorithms

### 4. Sturmian Sequences and Invertible Substitutions

It is known that a Sturmian sequence S can be defined as a coding of the orbit of rho (called the intercept of S) under a rotation of irrational angle alpha (called the slope). On the other hand, a fixed point of an invertible substitution is Sturmian. Naturally, there are two interrelated […]
Section: Combinatorics

### 5. Generation of Cubic graphs

We describe a new algorithm for the efficient generation of all non-isomorphic connected cubic graphs. Our implementation of this algorithm is more than 4 times faster than previous generators. The generation can also be efficiently restricted to cubic graphs with girth at least 4 or 5.
Section: Discrete Algorithms

### 6. Avoidance colourings for small nonclassical Ramsey numbers

The irredundant Ramsey number s - s(m, n) [upper domination Ramsey number u - u(m, n), respectively] is the smallest natural number s [u, respectively] such that in any red-blue edge colouring (R, B) of the complete graph of order s [u, respectively], it holds that IR(B) \textgreater= m or IR(R) […]
Section: Graph and Algorithms

### 7. A Combinatorial Approach to the Tanny Sequence

The Tanny sequence T (i) is a sequence defined recursively as T(i) = T(i - 1 - T(i - 1)) + T(i - 2 - T(i - 2)), T(0) = T(1) = T(2) = 1. In the first part of this paper we give combinatorial proofs of all the results regarding T(i), that Tanny proved in his paper "A well-behaved cousin of the […]
Section: Combinatorics

### 8. Colouring the Square of the Cartesian Product of Trees

We prove upper and lower bounds on the chromatic number of the square of the cartesian product of trees. The bounds are equal if each tree has even maximum degree.
Section: Graph and Algorithms