# Vol. 17 no.2

### 1. Minimum Number of Colors: the Turk’s Head Knots Case Study

An $r$-coloring of a knot diagram is an assignment of integers modulo $r$ to the arcs of the diagram such that at each crossing, twice the the number assigned to the over-arc equals the sum of the numbers assigned to the under-arcs, modulo $r$. The number of $r$-colorings is a knot invariant i.e., […]
Section: Combinatorics

### 2. The game chromatic number of trees and forests

While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests […]
Section: Graph Theory

### 3. The complexity of $P$<sub>4</sub>-decomposition of regular graphs and multigraphs

Let G denote a multigraph with edge set E(G), let &micro;(G) denote the maximum edge multiplicity in G, and let Pk denote the path on k vertices. Heinrich et al.(1999) showed that P4 decomposes a connected 4-regular graph G if and only if |E(G)| is divisible by 3. We show that P4 decomposes a […]
Section: Graph Theory

### 4. On graphs double-critical with respect to the colouring number

The colouring number col($G$) of a graph $G$ is the smallest integer $k$ for which there is an ordering of the vertices of $G$ such that when removing the vertices of $G$ in the specified order no vertex of degree more than $k-1$ in the remaining graph is removed at any step. An edge $e$ of a graph […]
Section: Graph Theory

### 5. Improving Vertex Cover as a Graph Parameter

Parameterized algorithms are often used to efficiently solve NP-hard problems on graphs. In this context, vertex cover is used as a powerful parameter for dealing with graph problems which are hard to solve even when parameterized by tree-width; however, the drawback of vertex cover is that bounding […]
Section: Discrete Algorithms

### 6. Disimplicial arcs, transitive vertices, and disimplicial eliminations

In this article we deal with the problems of finding the disimplicial arcs of a digraph and recognizing some interesting graph classes defined by their existence. A <i>diclique</i> of a digraph is a pair $V$ &rarr; $W$ of sets of vertices such that $v$ &rarr; $w$ is an arc for […]
Section: Graph Theory

### 7. Packing Plane Perfect Matchings into a Point Set

Given a set $P$ of $n$ points in the plane, where $n$ is even, we consider the following question: How many plane perfect matchings can be packed into $P$? For points in general position we prove the lower bound of &#x230A;log<sub>2</sub>$n$&#x230B;$-1$. For some special […]
Section: Graph Theory

### 8. Reducing the rank of a matroid

We consider the <i>rank reduction problem</i> for matroids: Given a matroid $M$ and an integer $k$, find a minimum size subset of elements of $M$ whose removal reduces the rank of $M$ by at least $k$. When $M$ is a graphical matroid this problem is the minimum $k$-cut problem, which […]
Section: Discrete Algorithms

### 9. Classical Automata on Promise Problems

Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required […]
Section: Automata, Logic and Semantics

### 10. On avoidance of patterns of the form σ-τ by words over a finite alphabet

Vincular or dashed patterns resemble classical patterns except that some of the letters within an occurrence are required to be adjacent. We prove several infinite families of Wilf-equivalences for $k$-ary words involving vincular patterns containing a single dash, which explain the majority of the […]
Section: Combinatorics

### 11. Symmetries of Monocoronal Tilings

The vertex corona of a vertex of some tiling is the vertex together with the adjacent tiles. A tiling where all vertex coronae are congruent is called monocoronal. We provide a classification of monocoronal tilings in the Euclidean plane and derive a list of all possible symmetry groups of […]
Section: Combinatorics

### 12. On the Dynamics of Systems of Urns

In this paper we present an analysis of some generalization of the classic urn and balls model. In our model each urn has a fixed capacity and initially is filled with white balls. Black balls are added to the system of connected urns and gradually displace white balls. We show a general form of […]
Section: Analysis of Algorithms

### 13. Cubical coloring — fractional covering by cuts and semidefinite programming

We introduce a new graph parameter that measures fractional covering of a graph by cuts. Besides being interesting in its own right, it is useful for study of homomorphisms and tension-continuous mappings. We study the relations with chromatic number, bipartite density, and other graph parameters. […]
Section: Graph Theory

### 14. Some undecidable problems about the trace-subshift associated to a Turing machine

We consider three problems related to dynamics of one-tape Turing machines: Existence of blocking configurations, surjectivity in the trace, and entropy positiveness. In order to address them, a reversible two-counter machine is simulated by a reversible Turing machine on the right side of its tape. […]
Section: Automata, Logic and Semantics

### 15. A relation on 132-avoiding permutation patterns

A permutation $&sigma;$ contains the permutation $&tau;$ if there is a subsequence of $&sigma;$ order isomorphic to $&tau;$. A permutation $&sigma;$ is $&tau;$-<i>avoiding</i> if it does not contain the permutation $&tau;$. For any $n$, the […]
Section: Combinatorics

### 16. The double competition multigraph of a digraph

In this article, we introduce the notion of the double competition multigraph of a digraph. We give characterizations of the double competition multigraphs of arbitrary digraphs, loopless digraphs, reflexive digraphs, and acyclic digraphs in terms of edge clique partitions of the multigraphs.
Section: Graph Theory