The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring problem from the point of view of split-coloring, such as criticality and the uniqueness of the minimum split-coloring. We discuss some properties of split-critical and uniquely split-colorable graphs. We describe constructions of such graphs […]

Section:
Graph and Algorithms

In a recent paper, Brlek, Jamet and Paquin showed that some extremal infinite smooth words are also infinite Lyndon words. This result raises a natural question: are they the only ones? If no, what do the infinite smooth words that are also Lyndon words look like? In this paper, we give the answer, proving that the only infinite smooth Lyndon words are m(\a ...

Section:
Combinatorics

A graph is a probe interval graph if its vertices can be partitioned into probes and nonprobes with an interval associated to each vertex so that vertices are adjacent if and only if their corresponding intervals intersect and at least one of them is a probe. A graph G = (V, E) is a tolerance graph if each vertex v is an element of V can be associated to an interval I(v) of the real line and a positive real number t(v) such that uv is an element of E if and only if vertical bar I(u) boolean AND […]

Section:
Graph and Algorithms

A graph with degree set \r, r + 1\ is said to be semiregular. A semiregular cage is a semiregular graph with given girth g and the least possible order. First, an upper bound on the diameter of semiregular graphs with girth g and order close enough to the minimum possible value is given in this work. As a consequence, these graphs are proved to be maximally connected when the girth g >= 7 is odd. Moreover an upper bound for the order of semiregular cages is given and, as an application, every […]

Section:
Graph and Algorithms

We show that there exist series-parallel graphs requiring Omega(n2(root log n)) area in any straight-line or poly-line grid drawing. Such a result is achieved in two steps. First, we show that, in any straight-line or poly-line drawing of K(2,n), one side of the bounding box has length Omega(n), thus answering two questions posed by Biedl et al. Second, we show a family of series-parallel graphs requiring Omega(2(root log n)) width and Omega(2(root log n)) height in any straight-line or […]

Section:
Graph and Algorithms

A set C of vertices of a graph G is P(3)-convex if v is an element of C for every path uvw in G with u, w is an element of C. We prove that it is NP-complete to decide for a given graph G and a given integer p whether the vertex set of G can be partitioned into p non-empty disjoint P(3)-convex sets. Furthermore, we study such partitions for a variety of graph classes.

Section:
Graph and Algorithms

In 1961, Erdos asked whether or not there exist words of arbitrary length over a fixed finite alphabet that avoid patterns of the form XX' where X' is a permutation of X (called abelian squares). This problem has since been solved in the affirmative in a series of papers from 1968 to 1992. Much less is known in the case of abelian k-th powers, i.e., words of the form X1X2 ... X-k where X-i is a permutation of X-1 for 2 <= i <= k. In this paper, we consider crucial words for abelian k-th […]

Section:
Combinatorics

The polynomial ring Z[x(11), ..., x(33)] has a basis called the dual canonical basis whose quantization facilitates the study of representations of the quantum group U-q(sl(3) (C)). On the other hand, Z[x(1 1), ... , x(33)] inherits a basis from the cluster monomial basis of a geometric model of the type D-4 cluster algebra. We prove that these two bases are equal. This extends work of Skandera and proves a conjecture of Fomin and Zelevinsky.

Section:
Combinatorics