Normal coloring - an equivalent version of Petersen coloring - is a special proper 5-edge-coloring of cubic graphs. Every edge in a normally colored graph is normal, i.e. it uses together with its four neighbours either only three colors or all five colors. Jaeger conjectured that every bridgeless cubic graph has a normal coloring. This conjecture, if true, imply for example Cycle double cover conjecture. Here we solve a weakened version of Jaeger's problem. We are looking for a proper 5-edge-coloring such that at least a part of the edges is normal. We show a coloring of generalized prisms with two thirds of the edges normal and a coloring of graphs without short cycles with almost half of the edges normal. Then we propose a new approach to normal coloring - chains. We use chains to prove that there cannot be only one single mistake in an almost normally colored graph. We also prove some statements about cuts in a normally colored graph which also follow from nowhere-zero Petersen flow. Finally, we examine a four-cycle in a normally colored graph. 1

A b-coloring of G is a proper vertex coloring such that there is a vertex in each color class, which is adjacent to at least one vertex in every other color class. Such a vertex is called a color-dominating vertex. The b-chromatic number of G is the largest k such that there is a b-coloring of G by k colors. Moreover, if for every integer k, between chromatic number and b-chromatic number, there exists a b-coloring of G by k colors, then G is b-continuous. Determining the b-chromatic number of a graph G and the decision whether the given graph G is b-continuous or not is NP-hard. Therefore, it is interesting to find new results on b-colorings and b-continuity for special graphs. In this thesis, for several graph classes some exact values as well as bounds of the b-chromatic number were ascertained. Among all we considered graphs whose independence number, clique number, or minimum degree is close to its order as well as bipartite graphs. The investigation of bipartite graphs was based on considering of the so-called bicomplement which is used to determine the b-chromatic number of special bipartite graphs, in particular those whose bicomplement has a simple structure. Then we studied some graphs whose b-chromatic number is close to its t-degree. At last, the b-continuity of some graphs is studied, for example, for graphs whose b-chromatic number was already established in this thesis. In particular, we could prove that Halin graphs are b-continuous.

The hypercube Qn is the graph whose vertices are the ordered n-tuples of zeros and ones, where two vertices are adjacent iff they differ in exactly one coordinate. A partial edge coloring f of a graph G is a mapping from a subset of edges of G to a set of colors; it is called proper if no pair of adjacent edges share the same color. A (possibly partial and unproper) coloring f is avoidable if there exists a proper coloring g such that no edge has the same color under f and g. An unavoidable coloring h is called minimal if it would be avoidable by letting any colored edge turn noncolored. We construct a computer program to find all minimal unavoidable edge colorings of Q3 using up to 3 colors, and draw some conclusions for general Qn.

We begin by introducing knots and links generally and identifying various geometric, polynomial, and integer-based knot and link invariants. Of particular importance to this paper are ternary operations and Niebrzydowski tribrackets defined in [12], [10]. We then introduce multi-tribrackets, ternary algebraic structures following the specified region coloring rules with di↵erent operations at multi-component and single component crossings. We will explore examples of each of the invariants and conclude with remarks on the direction of the introduced multi-tribracket theory.

Tait showed in 1878 that the Four Color Theorem is equivalent to being able to three-color the edges of any planar, three-regular, two-edge connected graph. Not surprisingly, this equivalent problem proved to be equally difficult. We consider the problem of fractional colorings, which resemble ordinary colorings but allow for some degree of cheating. Happily, it is known that every planar three-regular, two-edge connected graph is fractionally three-edge colorable. Is there an analogue to Tait’s Theorem which would allow us to derive the Fractional Four Color Theorem from this edge-coloring result?

We consider edge-colorings and flows problems in Graph Theory that are hard to solve for Class 2 graphs. Most of them are strongly related to some outstanding open conjectures, such as the Cycle Double Cover Conjecture, the Berge-Fulkerson Conjecture, the Petersen Coloring Conjecture and the Tutte's 5-flow Conjecture. We obtain some new restrictions on the structure of a possible minimum counterexample to the former two conjectures. We prove that the Petersen graph is, in a specific sense, the only graph that could appear in the Petersen Coloring Conjecture, and we provide evidence that led to propose an analogous of the Tutte's 5-flow conjecture in higher dimensions. We prove a characterization result and a sufficient condition for general graphs in relation to another edge-coloring problem, which is the determination of the palette index of a graph.

A b-coloring of G is a proper vertex coloring such that there is a vertex in each color class, which is adjacent to at least one vertex in every other color class. Such a vertex is called a color-dominating vertex. The b-chromatic number of G is the largest k such that there is a b-coloring of G by k colors. Moreover, if for every integer k, between chromatic number and b-chromatic number, there exists a b-coloring of G by k colors, then G is b-continuous. Determining the b-chromatic number of a graph G and the decision whether the given graph G is b-continuous or not is NP-hard. Therefore, it is interesting to find new results on b-colorings and b-continuity for special graphs. In this thesis, for several graph classes some exact values as well as bounds of the b-chromatic number were ascertained. Among all we considered graphs whose independence number, clique number, or minimum degree is close to its order as well as bipartite graphs. The investigation of bipartite graphs was based on considering of the so-called bicomplement which is used to determine the b-chromatic number of special bipartite graphs, in particular those whose bicomplement has a simple structure. Then we studied some graphs whose b-chromatic number is close to its t-degree. At last, the b-continuity of some graphs is studied, for example, for graphs whose b-chromatic number was already established in this thesis. In particular, we could prove that Halin graphs are b-continuous.:Contents 1 Introduction 2 Preliminaries 2.1 Basic terminology 2.2 Colorings of graphs 2.2.1 Vertex colorings 2.2.2 a-colorings 3 b-colorings 3.1 General bounds on the b-chromatic number 3.2 Exact values of the b-chromatic number for special graphs 3.2.1 Graphs with maximum degree at most 2 3.2.2 Graphs with independence number close to its order 3.2.3 Graphs with minimum degree close to its order 3.2.4 Graphs G with independence number plus clique number at most number of vertices 3.2.5 Further known results for special graphs 3.3 Bipartite graphs 3.3.1 General bounds on the b-chromatic number for bipartite graphs 3.3.2 The bicomplement 3.3.3 Bicomplements with simple structure 3.4 Graphs with b-chromatic number close to its t-degree 3.4.1 Regular graphs 3.4.2 Trees and Cacti 3.4.3 Halin graphs 4 b-continuity 4.1 b-spectrum of special graphs 4.2 b-continuous graph classes 4.2.1 Known b-continuous graph classes 4.2.2 Halin graphs 4.3 Further graph properties concerning b-colorings 4.3.1 b-monotonicity 4.3.2 b-perfectness 5 Conclusion Bibliography

A (closed) neighborhood-restricted 2-achromatic-coloring of a graph G is an assignment of colors to the vertices of G such that no more than two colors are assigned in any closed neighborhood. In other words, for every vertex v in G, the vertex v and its neighbors are in at most two different color classes. The 2-achromatic number is defined as the maximum number of colors in any 2-achromatic-coloring of G. We study the 2-achromatic number. In particular, we improve a known upper bound and characterize the extremal graphs for some other known bounds.

In this dissertation, we study two areas of interest in knot theory: Random knots in the unit cube, and the Yang-Baxter solutions constructed from Frobenius algebras. The study of random knots can be thought of as a model of DNA strings situated in confinement. A random knot with n vertices is a polygonal loop formed by selecting n distinct points in the unit cube, for a positive integer n, and connecting these points by straight line segments successively, such that the last point selected is joined with the first one. We present a step by step description of our algorithm and Maple codes for generating random knots in the unit cube, with a given vertex number n. To detect non-trivial knots, we use a knot invariant called the determinant. We present an algorithm and its Maple code for computing the determinant for random knots. For each vertex number n, we generate large number of random knots and form data sets of values of the determinant. Then we analyze our data sets in various ways. For instance, for each vertex number n, we form data sets of the number of p-colorable random knots by finding the set of prime divisors of each determinant output. We define the stick number for p-colorability to be the minimum number of line segments required to form a p-colorable knot. We use our data sets to find upper bounds for stick numbers for p-colorability, for primes p _ 191. We also find distributions of p-colorable knots and small determinant values. The second topic on random knots is the linking number of random links. A random link is a collection of disjoint random knots produced simultaneously. We present descriptions of our algorithm and its Maple code for constructing random links of two components, and calculating their linking numbers in detail. By running the code for 1000 times, for the vertex number n less than or equal to 30, we obtain data sets of linking numbers for two-component random links such that each component is a random knot with n vertices. Then we find the distribution of linking numbers and calculate upper bounds for the stick number for the linking numbers ` _ 15. The second area we investigate is applications of Fobenius algebras to knot theory. Chain complexes and Yang-Baxter solutions (R-matrices) are constructed by the skein theoretic approach using Frobenius algebras, and deformed R-matrices are constructed by using 2-cocyles. We compute cohomology groups, Yang-Baxter solutions and their cocycle deformations for group algebras, polynomial algebras and complex numbers. We construct knot and link invariants using these R-matrices from Frobenius algebras via Turaev’s criteria. Then a series of skein relations of the invariant are introduced for oriented knot or link diagrams. We also present calculations of the Frobenius skein invariant for various knots and links.

In this paper, we examine Fox colorings of virtual knots, and moves called k-swap moves defined for virtual knot diagrams. The k-swap moves induce a one-to-one correspondence between colorings before and after the move, and can be used to reduce the number of virtual crossings. For the study of colorings, we characterize families of alternating virtual knots to generalize (2, n)-torus knots, alternating pretzel knots, and alternating 2-bridge knots. The k-swap moves are then applied to prove a "virtualization" of the Kauffman-Harary conjecture, originally stated for classical knot diagrams, for the above families of virtual pretzel knot diagrams.