Given a graph G = (V, E), two players, Alice and Bob, alternate their turns to choose uncolored edges to be colored. Whenever an uncolored edge is chosen, it is colored by the least positive integer so that no monochromatic cycle is created. Alice¡¦s goal is to minimize the total number of colors used in the game, while Bob¡¦s goal is to maximize it. The game Grundy arboricity of G is the number of colors used in the game when both players use optimal strategies. This thesis discusses the game Grundy arboricity of graphs. It is proved that if a graph G has arboricity k, then the game Grundy arboricity of G is at most 3k − 1. If a graph G has an acyclic orientation D with maximum out-degree at most k, then the game Grundy arboricity of G is at most 3k − 2.

This thesis discusses graph marking game and graph colouring game. Suppose G=(V, E) is a graph. A marking game on G is played by two players, Alice and Bob, with Alice playing first. At the start of the game all vertices are unmarked. A play by either player consists of marking an unmarked vertex. The game ends when all vertices are marked. For each vertex v of G, write t(v)=j if v is marked at the jth step. Let s(v) denote the number of neighbours u of v for which t(u) < t(v), i.e., u is marked before v. The score of the game is $$s = 1+ max_{v in V} s(v).$$ Alice's goal is to minimize the score, while Bob's goal is to maximize it. The game colouring number colg(G) of G is the least s such that Alice has a strategy that results in a score at most s. Suppose r geq 1, d geq 0 are integers. In an (r, d)-relaxed colouring game of G, two players, Alice and Bob, take turns colouring the vertices of G with colours from a set X of r colours, with Alice having the first move. A colour i is legal for an uncoloured vertex x (at a certain step) if after colouring x with colour i, the subgraph induced by vertices of colour i has maximum degree at most d. Each player can only colour an uncoloured vertex with a legal colour. Alice's goal is to have all the vertices coloured, and Bob's goal is the opposite: to have an uncoloured vertex without legal colour. The d-relaxed game chromatic number of a graph G, denoted by $chi_g^{(d)}(G)$ is the least number r so that when playing the (r, d)-relaxed colouring game on G, Alice has a winning strategy. If d=0, then the parameter is called the game chromatic number of G and is also denoted by $chi_g(G)$. This thesis obtains upper and lower bounds for the game colouring number and relaxed game chromatic number of various classes of graphs. Let colg(PT_k) and colg(P) denote the maximum game colouring number of partial k trees and the maximum game colouring number of planar graphs, respectively. In this thesis, we prove that colg(PT_k) = 3k+2 and colg(P) geq 11. We also prove that the game colouring number colg(G) of a graph is a monotone parameter, i.e., if H is a subgraph of G, then colg(H) leq colg(G). For relaxed game chromatic number of graphs, this thesis proves that if G is an outerplanar graph, then $chi_g^{(d)}(G) leq 7-t$ for $t= 2, 3, 4$, for $d geq t$, and $chi_g^{(d)}(G) leq 2$ for $d geq 6$. In particular, the maximum $4$-relaxed game chromatic number of outerplanar graphs is equal to $3$. If $G$ is a tree then $chi_ g^{(d)}(G) leq 2$ for $d geq 2$.

No description available.

Includes vita. / Title from PDF of title page. / Document formatted into pages; contains 81 pages / Thesis (Ph.D.)--University of South Florida, 2002. / Includes bibliographical references. / Text (Electronic thesis) in PDF format. / ABSTRACT: Knot theory has rapidly expanded in recent years. New representations of braid groups led to an extremely powerful polynomial invariant, the Jones polynomial. Combinatorics applied to knot and link diagrams led to generalizations. Knot theory also has connections with other fields such as statistical mechanics and quantum field theory, and has applications in determining how certain enzymes act on DNA molecules, for example. The principal objective of this dissertation is to study the relations between knots and algebraic structures called quandles. A quandle is a set with a binary operation satisfying some properties related to the three Reidemeister moves. The study of quandles in relation to knot theory was intitiated by Joyce and Matveev. Later, racks and their (co)homology theory were defined by Fenn and Rourke. The rack (co)homology was also studied by Grana from the viewpoint of Hopf algebras. / ABSTRACT: Furthermore, a modified definition of homology theory for quandles was introduced by Carter, Jelsovsky, Kamada, Langford, and Saito to define state-sum invariants for knots and knotted surfaces, called quandle cocycle invariants. This dissertation studies the quandle cocycle invariants using extensions of quandles and knot colorings. We obtain a coloring of a knot by assigning elements of a quandle to the arcs of the knot diagram. Such colorings are used to define knot invariants by state-sum. For a given coloring, a 2-cocycle is assigned at each crossing as the Boltzmann weight. The product of the weights over all crossings is the contribution to the state-sum, which is the formal summation of the contributions over all possible colorings of the given knot diagram by a given quandle. Generalizing the cocycle invariant for knots to links, we define two kinds of invariants for links: a component-wise invariant, and an invariant defined as families of vectors. / ABSTRACT: Abelian extensions of quandles are also defined and studied. We give a formula for creating infinite families of abelian extensions of Alexander quandles. These extensions give rise to explicit formulas for computing 2-cocycles. The theory of quandle extensions parallels that of groups. Moreover, we investigate the notion of extending colorings of knots using quandle extensions. In particular, we show how the obstruction to extending the coloring contributes to the non-trivial terms of the cocycle invariants for knots and links. Moreover, we demonstrate the relation between these new cocycle invariants and Alexander matrices. / System requirements: World Wide Web browser and PDF reader. / Mode of access: World Wide Web.

Wireless communication is a rapidly growing segment of the communication industry, with the potential to provide low-cost, high-quality, and high-speed information exchange between portable devices. To harvest the available bandwidth efficientlyin a wireless network, they employ multiple orthogonal channels over multiple ra-dios at the nodes. In addition, nodes in these networks employ directional antennasas radios to improve spatial throughput. This dissertation develops algorithms forrouting and broadcasting with channel assignment in such networks. First, we com-pute the minimum cost path between a given source-destination pair with channelassignment on each link in the path such that no two transmissions interfere witheach other. Such a path must satisfy the constraint that no two consecutive links onthe path are assigned the same channel, referred to as "channel discontinuity con-straint." To compute such a path, we develop two graph expansion techniques basedon minimum cost perfect matching and dijkstra's algorithm. Through extensive sim-ulations, we study the effectiveness of the routing algorithms developed based onthe two expansion techniques and the benefits of employing the minimum cost per-fect matching based solution. Secondly, we study the benefits of sharing channelbandwidth across multiple flows. We model the routing and channel assignmentproblem in two different ways to account for the presence and absence of inter-flowbandwidth sharing. Benefits of multiple paths between a source-destination pairmotivates the problem of computing multiple paths between a source-destinationpair with channel assignment such that all the paths can be active simultaneouslyto achieve maximal flow between the pair in the considered network. Since finding even two such paths is NP-hard, we formulate the problem as an integer linearprogram and develop efficient heuristic to find these paths iteratively. Thirdly, wecompute a broadcast tree from a given root with channel assignment such that all the links in the broadcast tree can be active simultaneously without interferingwith each other. Since finding such a tree is an NP-hard problem, we formulatethe problem as an integer linear program (ILP) and develop heuristics to find thebroadcast tree with channel assignment. We evaluate and compare the performanceof the developed heuristics with respect to their success rate, average depth of theobtained tree, and average path length from root to a node in the network. Thisdissertation also analyzes the blocking performance of a channel assignment schemein a multi-channel wireless line network. We assume that the existing calls in thenetwork may be rearranged on different channels to accommodate an incoming call.The analysis is limited to single-hop calls with different transmission ranges.Finally, this dissertation evaluates the performance of disjoint multipath routingapproaches for all-to-all routing in packet-switched networks with respect to packetoverhead, path lengths, and routing table size. We develop a novel approach basedon cycle-embedding to obtain two node-disjoint paths between all source-destinationpairs with reduced number of routing table entries maintained at a node (hence thereduced look up time), small average path lengths, and less packet overhead. Westudy the trade-off between the number of routing table entries maintained at anode and the average length of the two disjoint paths by: (a) formulating the cycle-embedding problem as an integer linear program; and (b) developing a heuristic.We show that the number of routing table entries at a node may be reduced toat most two per destination using cycle-embedding approach, if the length of thedisjoint paths are allowed to exceed the minimum by 25%.

Classical vertex coloring problems ask for the minimum number of colors needed to color the vertices of a graph, such that adjacent vertices use different colors. Vertex coloring does have quite a few practical applications in communication theory, industry engineering and computer science. Such examples can be found in the book of Hansen and Marcotte. Deciding whether a graph is 3-colorable or not is a well-known NP-complete problem, even for triangle-free graphs. Intuitively, large girth may help reduce the chromatic number. However, in 1959, Erdos used the probabilitic method to prove that for any two positive integers g and k, there exist graphs of girth at least g and chromatic number at least k. Thus, restricting girth alone does not help bound the chromatic number. However, if we forbid certain tree structure in addition to girth restriction, then it is possible to bound the chromatic number. Randerath determined several such tree structures, and conjectured that if a graph is fork-free and triangle-free, then it is 3-colorable, where a fork is a star K1,4 with two branches subdivided once. The main result of this thesis is that Randerath’s conjecture is true for graphs with odd girth at least 7. We also give a proof that Randerath’s conjecture holds for graphs with maximum degree 4.

This thesis characterizes the problem of relative camera calibration in the context of three-dimensional volumetric reconstruction. The general effects of camera calibration errors on different parameters of the projection matrix are well understood. In addition, calibration error and Euclidean world errors for a single camera can be related via the inverse perspective projection. However, there has been little analysis of camera calibration for a large number of views and how those errors directly influence the accuracy of recovered three-dimensional models. A specific analysis of how camera calibration error is propagated to reconstruction errors using traditional voxel coloring algorithms is discussed. A review of the Voxel coloring algorithm is included and the general methods applied in the coloring algorithm are related to camera error. In addition, a specific, but common, experimental setup used to acquire real-world objects through voxel coloring is introduced. Methods for relative calibration for this specific setup are discussed as well as a method to measure calibration error. An analysis of effect of these errors on voxel coloring is presented, as well as a discussion concerning the effects of the resulting world-space error.

The first result of this thesis is a partial result in the direction of Steinberg's Conjecture. Steinberg's Conjecture states that any planar graph without cycles of length four or five is three colorable. Borodin, Glebov, Montassier, and Raspaud showed that planar graphs without cycles of length four, five, or seven are three colorable and Borodin and Glebov showed that planar graphs without five cycles or triangles at distance at most two apart are three colorable. We prove a statement that implies the first of these theorems and is incomparable with the second: that any planar graph with no cycles of length four through six or cycles of length seven with incident triangles distance exactly two apart are three colorable. The third and fourth chapters of this thesis are concerned with the study of Pfaffian orientations. A theorem proved by William McCuaig and, independently, Neil Robertson, Paul Seymour, and Robin Thomas provides a good characterization for whether or not a bipartite graph has a Pfaffian orientation as well as a polynomial time algorithm for that problem. We reprove this characterization and provide a new algorithm for this problem. In Chapter 3, we generalize a preliminary result needed to reprove this theorem. Specifically, we show that any internally 4-connected, non-planar bipartite graph contains a subdivision of K3,3 in which each path has odd length. In Chapter 4, we make use of this result to provide a much shorter proof using elementary methods of this characterization. In the fourth and fifth chapters we investigate flat embeddings. A piecewise-linear embedding of a graph in 3-space is flat if every cycle of the graph bounds a disk disjoint from the rest of the graph. We provide a structural theorem for flat embeddings that indicates how to build them from small pieces in Chapter 5. In Chapter 6, we present a class of flat graphs that are highly non-planar in the sense that, for any fixed k, there are an infinite number of members of the class such that deleting k vertices leaves the graph non-planar.

Singly-periodic (SP) and doubly-periodic (DP) graphs arc infinite graphs which have translational symmetries in one and two dimensions, respectively. The problem of counting the number of connected components in such graphs is investigated. A method for determining whether or not an SP graph is k-colourable for a given positive integer k is given, and the question of deciding k-colourability of DP graphs is discussed. Colourings of SP and DP graphs can themselves be either periodic or aperiodic, and properties which determine the symmetries of their colourings arc also explored.

Thesis (Ph. D.)--Rutgers University, 2007. / "Graduate Program in Operations Research." Includes bibliographical references (p. 57-61).