Roberts first studied the no-hole L(2, 1)-colorings and full L(2,1)-colorability of graphs. Fisher and Roberts discussed which graphs are full L(2,1)-colorable and which are not. They also posed three open questions, one of which is:
Let C∆ (λ) be the set of connected graphs other than trees with maximum degree ∆ and L(2, 1)-coloring number λ. Is the set of No Full Coloring (NFC) graphs in C4 (5) finite or infinite? In this paper, we construct an infinite class of NFC graphs in C4 (5), answering the question in the positive.
Here, for the first time, all connected quartic bipartite Cayley integral graphs are given including all non-obvious isomorphisms. Computations used previous results showing that all connected quartic bipartite integral graphs have one of 43 possible values for the number of vertices, all falling between 8 and 560. Recently the quartic Cayley integral graphs on finite abelian groups were determined but here we have found the graphs considering all groups.
Given a text T = T [1..N], the circular pattern discovery (CPD) problem is to identify ”interesting” circular patterns in T . Here, no specific input pattern is provided, and what is interesting is typically defined in terms of constraints in the search. We propose an algorithm to solve the approximate circular pattern discovery (ACPD) problem in O(km22 N2 ) worst case, and O(km22 N ) on average, where k is the error parameter, and m2 is the maximum length of a match. By exploiting the nature of the ACPD problem, the complexity can be reduced to O(m22 N2 ) worst case, and O(m22 N ) on average.
The multichromosomal circular median problem in the Double-Cut-and-Join (DCJ) distance asks to find, for three given genomes, a fourth circular genome that minimizes the sum of the mutual distances with the three other ones. This problem is NP-complete. We show here that, if the number of vertices of degree 3 in the breakpoint graph of the three input genomes is bounded, then the problem is tractable.
The Consecutive Ones Property is an important notion for binary matrices, both from a theoretical and applied point of view. Tucker gave in 1972 a characterization of matrices that do not satisfy the Consecutive Ones Property in terms of forbidden submatrices, the Tucker patterns. We describe here the first output-sensitive algorithm to enumerate all Tucker patterns of a binary matrix.
Let c(F) be the number of perfect pairs of F and c(G) be the maximum of c(F) over all (near-)one-factorizations F of G. Wagner showed that for odd n, c(Kn) ≥ n Φ(n) / 2 and for m and n which are odd and co-prime to each other, c(Kmn) ≥ 2 c(Km) c(Kn). In this note, we establish that both these results are equivalent in the sense that they both give rise to the same lower bound.
A new method that uses a vector representation for vertices as well as near-one-factors and produces a near-one-factorization of a complete graph of odd order is established in this paper. A novelty of the method is that it always produces n Φ(n) / 2 , n is the order of the graph, near-one-factors that are pairwise perfect. These perfect pairs can be easily identified from their representation. We also analyze the paths and cycles that occur in the union of a pair of near-one-factors of the proposed near-one-factorization. This analysis will be useful in the design of explicit acyclic edge coloring algorithms. We believe that this will also be helpful in addressing the famous Oberwolfach problem and in proving or disproving the perfect one-factorization conjecture.