Vol. 13 no. 1

1. Irregular edge coloring of 2-regular graphs

Cichacz, Sylwia ; Przybylo, Jakub.
Let G be a simple graph and let us color its edges so that the multisets of colors around each vertex are distinct. The smallest number of colors for which such a coloring exists is called the irregular coloring number of G and is denoted by c(G). We determine the exact value of the irregular […]
Section: Graph and Algorithms

2. Tree-width and large grid minors in planar graphs

Grigoriev, Alexander.
We show that for a planar graph with no g-grid minor there exists a tree-decomposition of width at most 5g - 6. The proof is constructive and simple. The underlying algorithm for the tree-decomposition runs in O(n(2) log n) time.
Section: Graph and Algorithms

3. Recursions and divisibility properties for combinatorial Macdonald polynomials

Loehr, Nicholas A. ; Niese, Elizabeth.
For each integer partition mu, let e (F) over tilde (mu)(q; t) be the coefficient of x(1) ... x(n) in the modified Macdonald polynomial (H) over tilde (mu). The polynomial (F) over tilde (mu)(q; t) can be regarded as the Hilbert series of a certain doubly-graded S(n)-module M(mu), or as a q, […]
Section: Combinatorics

4. Cycle transversals in bounded degree graphs

Groshaus, Marina ; Hell, Pavol ; Klein, Sulamita ; Nogueira, Loana Tito ; Protti, Fábio.
In this work we investigate the algorithmic complexity of computing a minimum C(k)-transversal, i.e., a subset of vertices that intersects all the chordless cycles with k vertices of the input graph, for a fixed k \textgreater= 3. For graphs of maximum degree at most three, we prove that this […]
Section: Graph and Algorithms

5. A de Bruijn - Erdos theorem and metric spaces

Chiniforooshan, Ehsan ; Chvatal, Vasek.
De Bruijn and Erdos proved that every noncollinear set of n points in the plane determines at least n distinct lines. Chen and Chvatal suggested a possible generalization of this theorem in the framework of metric spaces. We provide partial results in this direction.
Section: Combinatorics

6. Negative bases and automata

Frougny, Christiane ; Lai, Anna Chiara.
We study expansions in non-integer negative base -beta introduced by Ito and Sadahiro. Using countable automata associated with (-beta)-expansions, we characterize the case where the (-beta)-shift is a system of finite type. We prove that, if beta is a Pisot number, then the (-beta)-shift is a sofic […]
Section: Automata, Logic and Semantics

7. Deterministic Recurrent Communication and Synchronization in Restricted Sensor Network

Fernández Anta, Antonio ; Mosteiro, Miguel ; Thraves Caro, Christopher.
Monitoring physical phenomena in Sensor Networks requires guaranteeing permanent communication between nodes. Moreover, in an effective implementation of such infrastructure, the delay between any two consecutive communications should be minimized. The problem is challenging because, in a restricted […]
Section: Distributed Computing and Networking