Vol. 13 no. 2

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

Person, Yury ; Schacht, Mathias.
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

Jelinkova, Eva ; Suchy, Ondrej ; Hlineny, Petr ; Kratochvil, Jan.
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. In this paper, we continue the study of computational complexity aspects of Seidel's switching, concentrating on Fixed Parameter Complexity. Among other results we show that switching to a graph with […]
Section: Graph and Algorithms

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

Pitman, Damien.
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 converges weakly (in the number of variables) to a distribution determined by a Poisson random variable. The number of satisfying assignments or solutions is known to grow exponentially in the number of […]
Section: Graph and Algorithms

4. Sturmian Sequences and Invertible Substitutions

Peng, Li ; Tan, Bo.
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 questions: (1) Given an invertible substitution, we know that its fixed point is Sturmian. What is the slope and intercept? (2) Which kind of Sturmian sequences can be fixed by certain non-trivial invertible […]
Section: Combinatorics

5. Generation of Cubic graphs

Brinkmann, Gunnar ; Goedgebeur, Jan ; Mckay, Brendan D..
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

Burger, Alewyn Petrus ; Vuuren, Jan H., .
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) \textgreater= n [Gamma (B) \textgreater= m or Gamma(R) \textgreater= n, respectively], where Gamma and IR denote respectively the upper domination number and the irredundance number of a graph. […]
Section: Graph and Algorithms

7. A Combinatorial Approach to the Tanny Sequence

Das, Anita.
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 Hofstadter sequence", Discrete Mathematics, 105(1992), pp. 227-239, using algebraic means. In most cases our proofs turn out to be simpler and shorter. Moreover, they give a "visual" […]
Section: Combinatorics

8. Colouring the Square of the Cartesian Product of Trees

Wood, David, .
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