Snarks are a historical class of cubic graphs with peculiar properties motivated by the Four-Color Theorem. In nearly 100 years of search, since its definition by Peter Guthrie Tait in 1880, only five such graphs were identified which motivated Martin Gardner in 1976 to call them snark, a mysterious creature. In 1975, Rufus Isaacs introduced a method known as dot product, which allowed the construction of new snarks from known snarks, and presented the first infinite family of snarks. A new method proposed in 1996 by Martin Kochol allowed to obtaining new snarks from smaller graphs, known as Kochol superposition. However, this method was usually used to obtain snarks with large girth. We applied the Kochol superposition to known snarks: the family of Goldberg snarks (known to be Type 1) and a girth 4 snark recently discovered by Gunnar Brinkmann et al. (known to be Type 2). Surprisingly, when we apply the Kochol superposition to a Type 1 snark with a Type 2 snark, we can obtain new families of snarks of distinct Types: Type 1 and Type 2.

A biclique q-coloring is an assignment of q-colors to the vertices of a graph G, so that no biclique (maximal set of vertices that induces a complete bipartite subgraph of G with at least one edge) is monochromatic. Inspired by the coloring game, we introduce the biclique q-coloring game played on a graph G defined as follows. Two players, Alice and Bob, alternately color the vertices of a graph G using q colors. Alice's goal is to color the vertices of G so that no biclique is monochromatic, and Bob tries to prevent this. Both players play optimally and respect the following rule: if a biclique is fully colored, then there exist at least two vertices in the biclique with different colors. In this paper, we prove that the biclique q-coloring game is PSPACE-complete and study the game in powers of paths Pkn.

A q-total coloring of G is an assignment of q colors to the vertices or edges of G, so that adjacent or incident elements have different colors. The Total Coloring Conjecture (TCC) asserts that a total coloring of a graph G has at least ∆ + 1 and at most ∆ + 2 colors. Rosenfeld has shown that the total chromatic number of a cubic graph is either 4 (Type 1) or 5 (Type 2). We present Type 1 new infinite families of snarks (cubic bridgeless graphs of chromatic index 4) obtained by the Kochol superposition of Goldberg with t-Semiblowup snarks. These results provide evidence of a negative answer for the question proposed by Cavicchioli et al. (2003) about the smallest order of a Type 2 snark of girth at least 5.

A fullerene graph is a planar, cubic, 3-connected graph with only pentagonal and hexagonal faces. In 2012, Andova and Škrekovski conjectured that the diameter of every fullerene graph with n vertices is at least √5n/3 - 1. They computed this lower bound by studying a particular class of fullerene graphs named spherical with icosahedral symmetry. We denote these graphs by Gi,j, by setting two parameters i, j ε N*, such that i ≤ j. In their study, Andova and Škrekovski offered numerous properties of hexagonal lattices and calculated the diameter of two remarkable spherical fullerene graphs: G0,j and Gj,j. Although the conjecture is valid for these two distinct classes, it remains open deciding whether the premise is proper for all spherical fullerene graphs Gi,j. In this work, we present the first class of fullerene graphs with icosahedral symmetry that do not satisfy Andova and Skrekovski's conjecture, which refutes that this conjecture is valid for all spherical graphs. We also focus on showing properties of spherical fullerene graphs and the hexagonal lattice itself. We prove that all graphs Gi,j have a reduction of the form Gi-k,j-k, where k ≤ i, such that their triangular faces are entirely contained in the triangular faces of Gi,j. In addition, by setting k = i, this property states a particular link among Gi,j, Gi-1, j-1, • • •, G0,j-i, creating a chain of reductions of Gi,j, which implies that diam (Gi,j) ≥ diam (G0,j-i).

The search for counterexamples to the Four Color Conjecture originated snarks, a very special class of cubic graphs. In this paper, we consider the equitable total coloring of snarks. A total coloring is equitable if the number of elements colored with each color differs by at most one, and the least integer for which a graph has such a coloring is called its equitable total chromatic number. In 2002, Wang conjectured that the equitable total chromatic number of a graph is at most ∆ + 2, and this was proved for cubic graphs. Therefore, the equitable total chromatic number of a cubic graph is either 4 or 5. We provide evidence to a negative answer to the question proposed in 2016 about the existence of a Type 1 cubic graph with girth greater than 4 and equitable total chromatic number 5, by determining equitable 4-total colorings for every member of three infinite families of snarks with girth 5.

The (a,b)-monochromatic transversal game is an avoider-enforcer combinatorial game in which two players, Alice and Bob, alternately take turns colouring respectively a vertices in red and b vertices in blue of a hypergraph. She wins the game by obtaining a red transversal while he wins by obtaining a monochromatic blue hyperedge. Also, both players are enabled to start the game and they play optimally. In this paper, we analyze the game played on biclique-hypergraphs of powers of paths and of powers of cycles showing strategies that, depending on the choice of the parameters a and b, allow a specific player to win the game.

MOTIVATION: The traditional view of cancer evolution states that a cancer genome accumulates a sequential ordering of mutations over a long period of time. However, in recent years it has been suggested that a cancer genome may instead undergo a one-time catastrophic event, such as chromothripsis, where a large number of mutations instead occur simultaneously. A number of potential signatures of chromothripsis have been proposed. In this work, we provide a rigorous formulation and analysis of the 'ability to walk the derivative chromosome' signature originally proposed by Korbel and Campbell. In particular, we show that this signature, as originally envisioned, may not always be present in a chromothripsis genome and we provide a precise quantification of under what circumstances it would be present. We also propose a variation on this signature, the H/T alternating fraction, which allows us to overcome some of the limitations of the original signature. RESULTS: We apply our measure to both simulated data and a previously analyzed real cancer dataset and find that the H/T alternating fraction may provide useful signal for distinguishing genomes having acquired mutations simultaneously from those acquired in a sequential fashion. AVAILABILITY AND IMPLEMENTATION: An implementation of the H/T alternating fraction is available at https://bitbucket.org/oesperlab/ht-altfrac. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Important papers have appeared recently on the problem of indexing binary strings for jumbled pattern matching, and further lowering the time bounds in terms of the input size would now be a breakthrough with broad implications. We can still make progress on the problem, however, by considering other natural parameters. Badkobeh et al. (IPL, 2013) and Amir et al. (TCS, 2016) gave algorithms that index a binary string in O(n + r^2 log r) time, where n is the length and r is the number of runs, and Giaquinta and Grabowski (IPL, 2013) gave one that runs in O(n + r^2) time. In this paper we propose a new and very simple algorithm that also runs in O(n + r^2) time and can be extended either so that the index returns the position of a match (if there is one), or so that the algorithm uses only O(n) bits of space instead of O(n) words.

We determine complexity of computing the DCJ-indel distance, when DCJ and indel operations have distinct constant costs, by showing an exact formula that can be computed in linear time for any choice of (constant) costs for DCJ and indel operations. We additionally consider the problem of triangular inequality disruption and propose an algorithmically efficient correction on each member of the family of DCJ-indel.

BACKGROUND: The double-cut-and-join (DCJ) is a model that is able to efficiently sort a genome into another, generalizing the typical mutations (inversions, fusions, fissions, translocations) to which genomes are subject, but allowing the existence of circular chromosomes at the intermediate steps. In the general model many circular chromosomes can coexist in some intermediate step. However, when the compared genomes are linear, it is more plausible to use the so-called restricted DCJ model, in which we proceed the reincorporation of a circular chromosome immediately after its creation. These two consecutive DCJ operations, which create and reincorporate a circular chromosome, mimic a transposition or a block-interchange. When the compared genomes have the same content, it is known that the genomic distance for the restricted DCJ model is the same as the distance for the general model. If the genomes have unequal contents, in addition to DCJ it is necessary to consider indels, which are insertions and deletions of DNA segments. Linear time algorithms were proposed to compute the distance and to find a sorting scenario in a general, unrestricted DCJ-indel model that considers DCJ and indels. RESULTS: In the present work we consider the restricted DCJ-indel model for sorting linear genomes with unequal contents. We allow DCJ operations and indels with the following constraint: if a circular chromosome is created by a DCJ, it has to be reincorporated in the next step (no other DCJ or indel can be applied between the creation and the reincorporation of a circular chromosome). We then develop a sorting algorithm and give a tight upper bound for the restricted DCJ-indel distance. CONCLUSIONS: We have given a tight upper bound for the restricted DCJ-indel distance. The question whether this bound can be reduced so that both the general and the restricted DCJ-indel distances are equal remains open.