Narrow Results

In this paper, we generalize virtual knot theory to multi-virtual knot theory where there are a multiplicity of virtual crossings. Each virtual crossing type can detour over the other virtual crossing types, and over classical or immersed crossings. New invariants of multi-virtual knots and links are introduced and new problems that arise are described. We show how the extensions of the Penrose coloring evaluation for trivalent plane graphs and our generalizations of this to non-planar graphs and arbitrary numbers of colors acts as a motivation for the construction of the multi-virtual theory.

The inverted weak Schur number $Ŝ(k,n)$ refers to the smallest positive integer $N$ such that any $n$-coloring of $\{1,2,\dots ,N\}$ inevitably contains a solution to the equation:

A k-forward numbering of a graph is a labeling of the nodes with integers such that each node has less than k neighbors whose labels are equal or larger. Distributed algorithms that reach a legitimate state, starting from any illegitimate state, are called self-stabilizing. We obtain three self-stabilizing (s-s) algorithms for finding a k-forward numbering, provided one exists. One such algorithm also finds the k-height numbering of graph, generalizing s-s algorithms by Bruell et al. [4] and Antonoiu et al. [1] for finding the center of a tree. Another k-forward numbering algorithm runs in polynomial time. The motivation of k-forward numberings is to obtain new s-s graph coloring algorithms. We use a k-forward numbering algorithm to obtain an s-s algorithm that is more general than previous coloring algorithms in the literature, and which k-colors any graph having a k-forward numbering. Special cases of the algorithm 6-color planar graphs, thus generalizing an s-s algorithm by Ghosh and Karaata [13], as well as 2-color trees and 3-color series-parallel graphs. We discuss how our s-s algorithms can be extended to the synchronous model.

The file transfer scheduling problem was introduced and studied by Coffman, Garey, Johnson and LaPaugh. The problem is to schedule transfers of a large collection of files between various nodes of a network under port constraint so as to minimize the overall finishing time. This paper extends their model to include communication channel constraint in addition to port constraint. We formulate the problem with both port and channel constraints as a new type of edge-coloring of multigraphs, called an fg-edge-coloring, and give an efficient approximation algorithm with absolute worst-case ratio 3/2.

In salt farms of Thailand, saline ground water is pumped up and then solar-evaporated to produce salt for commercial purpose. However, when they continue to precipitate salt in the same pools, the product is stained yellow or brown in color. In order to recover only white salt, workers cut trees and create a new pool next to the old one. Due to this practice, year by year, salt-farming area loses vegetation cover and expands barren section of salt damage. In order to understand the changes of in salt grains, salt was collected and measured by PIXE. The result indicates that manganese is clearly responsible for the coloring, and possibly also irons. This information is expected to base the discussion to stop deforestation in the salt-damaged area.

An optimal parallel algorithm is presented for coloring an interval graph using minimum number of colors. The proposed parallel algorithm takes time with P processors on an EREW PRAM.

Balanced colorings of networks correspond to flow-invariant synchrony spaces. It is known that the coarsest balanced coloring is equivalent to nodes having isomorphic infinite input trees, but this condition is not algorithmic. We provide an algorithmic characterization: two nodes have the same color for the coarsest balanced coloring if and only if their $(n-1)$th input trees are isomorphic, where $n$ is the number of nodes. Here $n-1$ is the best possible. The proof is analogous to that of Leighton’s theorem in graph theory, using the universal cover of the network and the notion of a symbolic adjacency matrix to set up a partition refinement algorithm whose output is the coarsest balanced coloring. The running time of the algorithm is cubic in $n$.

We exhibit a hierarchically hyperbolic group for which no hierarchically hyperbolic structure is colorable, answering an (implicit) question of Durham–Minsky–Sisto.

A quandle is a set with a binary operation satisfying some properties. A quandle homomorphism is a map between quandles preserving the structure of their binary operations. A knot determines a quandle called a knot quandle. We show that the number of all quandle homomorphisms of a knot quandle of a knot to an Alexander quandle is completely determined by Alexander polynomials of the knot. Further we show that the set of all quandle homomorphisms of a knot quandle to an Alexander quandle has a module structure.

We prove that if a surface-knot diagram is colored by a specific quandle non-trivially, then any diagram of the surface-knot consists of at least four broken sheets. In particular, the minimal number of broken sheets for the spun trefoil is shown to be exactly four.

Fox's shadow p-colorings of a knot K define two kinds of Laurent polynomials, Φ_p(K) and , as invariants of K. We prove that the equality holds for any knot K. Also we prove that, if the p-coloring number of K is equal to p², then has the form for some N ∈ ℤ_p.

We define the fundamental quandle of a spatial graph and several invariants derived from it. In the category of graph tangles, we define an invariant based on the walks in the graph and cocycles from nonabelian quandle cohomology.

In this paper, we study the colorability of link diagrams by the Alexander quandles. We show that if the reduced Alexander polynomial Δ_L(t) is vanishing, then L admits a non-trivial coloring by any non-trivial Alexander quandle Q, and that if Δ_L(t) = 1, then L admits only the trivial coloring by any Alexander quandle Q, also show that if Δ_L(t) ≠ 0, 1, then L admits a non-trivial coloring by the Alexander quandle Λ/(Δ_L(t)).

For a 1- or 2-dimensional knot, we give a lower bound log₂ n + 1 of the minimum number of distinct colors for all effective n-colorings. In particular, we prove that any effectively 9-colorable 1- or ribbon 2-knot is presented by a diagram where exactly five colors of nine are assigned to the arcs or sheets.

We discuss the connection between colorings of a link diagram and the Goeritz matrix.

We prove that for any odd $n\ge 3$, the $n$-palette number of any effectively $n$-colorable $2$-bridge knot is equal to $2+\lfloor {log}_{2}n\rfloor$. Namely, there is an effectively $n$-colored diagram of the $2$-bridge knot such that the number of distinct colors that appeared in the diagram is exactly equal to $2+\lfloor {log}_{2}n\rfloor$.

In V. O. Manturov, On free knots, preprint (2009), arXiv:math.GT/0901.2214], the second named author constructed the bracket invariant $[\cdot ]$ of virtual knots valued in pictures (linear combinations of virtual knot diagrams with some crossing information omitted), such that for many diagrams $K$, the following formula holds: $[K]=\tilde{K}$, where $\tilde{K}$ is the underlying graph of the diagram, i.e. the value of the invariant on a diagram equals the diagram itself with some crossing information omitted. This phenomenon allows one to reduce many questions about virtual knots to questions about their diagrams. In [S. Nelson, M. E. Orrison and V. Rivera, Quantum enhancements and biquandle brackets, preprint (2015), arXiv:math.GT/1508.06573], the authors discovered the following phenomenon: having a biquandle coloring of a certain knot, one can enhance various state-sum invariants (say, Kauffman bracket) by using various coefficients depending on colors. Taking into account that the parity can be treated in terms of biquandles, we bring together the two ideas from these papers and construct the picture-valued parity-biquandle bracket for classical and virtual knots. This is an invariant of virtual knots valued in pictures. Both the parity bracket and Nelson–Orrison–Rivera invariants are partial cases of this invariant, hence this invariant enjoys many properties of various kinds. Recently, the authors together with E. Horvat and S. Kim have found that the picture-valued phenomenon works in the classical case.

The method of distinguishing knots and links using the colorability of their diagrams was invented by Ralph Fox [2]. As generalization of this method, we introduce certain method of distinguishing spatial graphs.

The intersection graph I_TΓ(R) of gamma sets in the total graph T_Γ(R) of a commutative ring R, is the undirected graph with vertex set as the collection of all γ-sets in the total graph of R and two distinct vertices u and v are adjacent if and only if u ∩ v ≠ ∅. Tamizh Chelvam and Asir [The intersection graph of gamma sets in the total graph I, to appear in J. Algebra Appl.] studied about I_TΓ(R) where R is a commutative Artin ring. In this paper, we continue our interest on I_TΓ(R) and actually we study about Eulerian, Hamiltonian and pancyclic nature of I_TΓ(R). Further, we focus on certain graph theoretic parameters of I_TΓ(R) like the independence number, the clique number and the connectivity of I_TΓ(R). Also, we obtain both vertex and edge chromatic numbers of I_TΓ(R). In fact, it is proved that if R is a finite commutative ring, then χ(I_TΓ(R)) = ω(I_TΓ(R)). Having proved that I_TΓ(R) is weakly perfect for all finite commutative rings, we further characterize all finite commutative rings for which I_TΓ(R) is perfect. In this sequel, we characterize all commutative Artin rings for which I_TΓ(R) is of class one (i.e. χ′(I_TΓ(R)) = Δ(I_TΓ(R))). Finally, it is proved that the vertex connectivity and edge connectivity of I_TΓ(R) are equal to the degree of any vertex in I_TΓ(R).

Consider an M × N chess board with each space colored one of K colors. A chromatic rectangle is a rectangular collection of spaces with all four corner spaces colored the same. An M × N : K NCR board is an M × N board for which there exists a K coloring with no chromatic rectangles. If every K coloring includes a chromatic rectangle, then that board is called an M × N : K CR board. The classification as NCR versus CR has been settled for K ∈ {1, 2, 3} and all positive integers N and M.

Note that transposition, or interchanging rows, columns, or colors, will preserve the existence of chromatic rectangles within a coloring. With this in mind, two colorings of a board are called equivalent if one can be produced from the other by such manipulations. This paper establishes that all 10 × 10 : 3 NCR colorings are equivalent.

The results stem from characterizations of NCR colorings. These characterizations permit devising and implementing a backtracking algorithm for finding NCR colorings within a significantly restricted search space. In the 10 × 10 : 3 case, the restricted search space is small enough to complete an exhaustive search in about an hour.

Several NCR colorings for larger boards, with K > 3, are also included.