-colorings and -bipartite graphs.
Palindromes in infinite ternary words
We study infinite words u over an alphabet satisfying the property , where denotes the number of palindromic factors of length n occurring in the language of u. We study also infinite words satisfying a stronger property : every palindrome of u has exactly one palindromic extension in u. For binary words, the properties and coincide and these properties characterize Sturmian words, i.e., words with the complexity C(n) = n + 1 for any . In this paper, we focus on ternary infinite...
Palindromic complexity of infinite words associated with non-simple Parry numbers
We study the palindromic complexity of infinite words , the fixed points of the substitution over a binary alphabet, , , with , which are canonically associated with quadratic non-simple Parry numbers .
Palindromic complexity of infinite words associated with non-simple Parry numbers
We study the palindromic complexity of infinite words uβ, the fixed points of the substitution over a binary alphabet, φ(0) = 0a1, φ(1) = 0b1, with a - 1 ≥ b ≥ 1, which are canonically associated with quadratic non-simple Parry numbers β.
Palindromic complexity of infinite words associated with simple Parry numbers
A simple Parry number is a real number such that the Rényi expansion of is finite, of the form . We study the palindromic structure of infinite aperiodic words that are the fixed point of a substitution associated with a simple Parry number . It is shown that the word contains infinitely many palindromes if and only if . Numbers satisfying this condition are the so-called confluent Pisot numbers. If then is an Arnoux-Rauzy word. We show that if is a confluent Pisot number then...
Palindromic continued fractions
In the present work, we investigate real numbers whose sequence of partial quotients enjoys some combinatorial properties involving the notion of palindrome. We provide three new transendence criteria, that apply to a broad class of continued fraction expansions, including expansions with unbounded partial quotients. Their proofs heavily depend on the Schmidt Subspace Theorem.
Parallel algorithms on interval graphs
Parameters of bar -visibility graphs.
Parikh test sets for commutative languages
A set T ⊆ L is a Parikh test set of L if c(T) is a test set of c(L). We give a characterization of Parikh test sets for arbitrary language in terms of its Parikh basis, and the coincidence graph of letters.
Parity vertex colorings of binomial trees
We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.
Parity vertex colouring of graphs
A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T),...
Partial covers of graphs
Given graphs G and H, a mapping f:V(G) → V(H) is a homomorphism if (f(u),f(v)) is an edge of H for every edge (u,v) of G. In this paper, we initiate the study of computational complexity of locally injective homomorphisms called partial covers of graphs. We motivate the study of partial covers by showing a correspondence to generalized (2,1)-colorings of graphs, the notion stemming from a practical problem of assigning frequencies to transmitters without interference. We compare the problems of...
Partially complemented representations of digraphs.
Pascal's triangle, complexity and automata. (Triangle de Pascal, complexité et automates.)
Paths through fixed vertices in edge-colored graphs
We study the problem of finding an alternating path having given endpoints and passing through a given set of vertices in edge-colored graphs (a path is alternating if any two consecutive edges are in different colors). In particular, we show that this problem in NP-complete for 2-edge-colored graphs. Then we give a polynomial characterization when we restrict ourselves to 2-edge-colored complete graphs. We also investigate on (s,t)-paths through fixed vertices, i.e. paths of length s+t such that...
Pattern avoidance in partial words over a ternary alphabet
Blanched-Sadri and Woodhouse in 2013 have proven the conjecture of Cassaigne, stating that any pattern with m distinct variables and of length at least 2m is avoidable over a ternary alphabet and if the length is at least 3 2m−1 it is avoidable over a binary alphabet. They conjectured that similar theorems are true for partial words - sequences, in which some characters are left “blank”. Using method of entropy compression, we obtain the partial words version of the theorem for ternary words
Pattern occurrence in the dyadic expansion of square root of two and an analysis of pseudorandom number generators.
Pebbling dynamic graphs in minimal space
Performance analysis of demodulation with diversity -- A combinatorial approach I: Symmetric function theoretical methods.
Performance considerations on a random graph model for parallel processing