Vol. 12 no. 5

1. Split-critical and uniquely split-colorable graphs

Ekim, Tınaz ; Ries, Bernard ; De Werra, Dominique.
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 […]
Section: Graph and Algorithms

2. A characterization of infinite smooth Lyndon words

Paquin, Geneviève.
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, […]
Section: Combinatorics

3. Linear Time Recognition Algorithms and Structure Theorems for Bipartite Tolerance Graphs and Bipartite Probe Interval Graphs

Brown, David E. ; Busch, Arthur H. ; Isaak, Garth.
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 […]
Section: Graph and Algorithms

4. Some properties of semiregular cages

Balbuena, Camino ; Marcote, Xavier ; Gonzalez-Moreno, Diego.
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 […]
Section: Graph and Algorithms

5. Lower Bounds on the Area Requirements of Series-Parallel Graphs

Frati, Fabrizio.
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), […]
Section: Graph and Algorithms

6. Convex Partitions of Graphs induced by Paths of Order Three

Centeno, C. C. ; Dantas, S. ; Dourado, M. C. ; Rautenbach, Dieter ; Szwarcfiter, Jayme Luiz.
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. […]
Section: Graph and Algorithms

7. Crucial abelian k-power-free words

Glen, Amy ; Halldorsson, Bjarni V. ; Kitaev, Sergey.
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 […]
Section: Combinatorics

8. The cluster and dual canonical bases of Z[x(11), ..., x(33)] are equal

Rhoades, Brendon.
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 […]
Section: Combinatorics