More on the complexity of cover graphs
In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem.
Morphic and automatic words: maximal blocks and Diophantine approximation
Morphing planar graphs in spherical space.
Morphismes sturmiens et règles de Rauzy
Nous donnons une caractérisation complète de tous les morphismes binaires qui préservent les mots sturmiens et montrons que les mots infinis engendrés par ces morphismes sont rigides.
Morphisms fixing words associated with exchange of three intervals
We consider words coding exchange of three intervals with permutation (3,2,1), here called 3iet words. Recently, a characterization of substitution invariant 3iet words was provided. We study the opposite question: what are the morphisms fixing a 3iet word? We reveal a narrow connection of such morphisms and morphisms fixing Sturmian words using the new notion of amicability.
Morphisms preserving the set of words coding three interval exchange
Any amicable pair ϕ, ψ of Sturmian morphisms enables a construction of a ternary morphism η which preserves the set of infinite words coding 3-interval exchange. We determine the number of amicable pairs with the same incidence matrix in SL±(2,ℕ) and we study incidence matrices associated with the corresponding ternary morphisms η.
Morphisms preserving the set of words coding three interval exchange∗∗∗
Any amicable pair ϕ, ψ of Sturmian morphisms enables a construction of a ternary morphism η which preserves the set of infinite words coding 3-interval exchange. We determine the number of amicable pairs with the same incidence matrix in SL±(2,ℕ) and we study incidence matrices associated with the corresponding ternary morphisms η.
Motion planning in cartesian product graphs
Let G be an undirected graph with n vertices. Assume that a robot is placed on a vertex and n − 2 obstacles are placed on the other vertices. A vertex on which neither a robot nor an obstacle is placed is said to have a hole. Consider a single player game in which a robot or obstacle can be moved to adjacent vertex if it has a hole. The objective is to take the robot to a fixed destination vertex using minimum number of moves. In general, it is not necessary that the robot will take a shortest path...
Multicolored isomorphic spanning trees in complete graphs.
Multidimensional linear congruential graphs
Multiprocessor Interconnection Networks
Multi-static enumeration of two-stack sortable permutations.
Nahlédnutí pod pokličku kombinatoriky na nekonečných slovech
Navigating clustered graphs using force-directed methods.
Neochromatica
We create and discuss several modifications to traditional graph coloring. In particular, we classify various notions of coloring in a proper hierarchy. We concentrate on grid graphs whose colorings can be represented by natural number entries in arrays with various restrictions.
New bounds for codes identifying vertices in graphs.
New lower bound on the number of ternary square-free words.
New results on generalized graph coloring.
New temperatures in Domineering.
Nombre de sauts et graphes série-parallèles