Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 44 for “"edge-coloring"”.
-
Edge coloring BIBDS and constructing MOELRs
… that each copy of the Kk contains at most one edge from each Kv. This is called a proper edge coloring (Hurd, Sarvate, [29]). The majority of the content in this section is a wide variety of examples to explain the constructions used in Chapters 3 and 4. In Chapters 3 and 4 we investigate how …
-
Edge-Coloring Planar Graphs and the Cycling Conjecture
… has degree r and any odd subset has at least r edges leaving it. This thesis focuses on the conjecture that any planar r-graph can be edge-colored with r colors. Past work has shown that the conjecture holds for r ≤ 8, but it becomes more difficult with each increase of r. We consider what …
-
Edge-coloring k-uniform hypergraphs of large maximum degree
… work towards a conjecture of Alon and Kim about coloring the edges of $k$-uniform $t$-simple hypergraphs. A hypergraph is $k$-uniform if every edge contains exactly $k$ vertices, and $t$-simple if any two edges intersect in at most $t$ vertices. The chromatic index of a hypergraph $H$, denoted …
-
Fractional edge coloring for wireless link scheduling in the physical interference mode
… the Link Scheduling problem as a Fractional Edge-Coloring problem. A Linear Programming (LP) formulation with exponential complexity on the graph size and an algorithm to aid efficiently building such models are introduced. Finally, a considerable amount of experiments were run in order to …
-
Edge coloring of simple graphs and edge -face coloring of simple plane graphs
… results.;Given a simple plane graph G, an edge-face k-coloring of G is a function &phis; : E(G) ∪ F(G) {lcub}1, ···, k{rcub} such that, for any two adjacent elements a, b ∈ E(G) ∪ F(G), &phis;( a) ≠ &phis;(b). Denote chie( G), chief(G), Delta( G) the edge chromatic number, the edge-face …
-
Effects of n>m Clos networks on edge coloring and matrix decomposition algorithms
… in this thesis are n > m Clos networks on edge coloring and matrix decomposition algorithms. This work uses a two-fold approach to examine the effects of n > m Clos networks on edge coloring and matrix decomposition algorithms. First, edge coloring and matching on bipartite multigraphs are …
-
Interval Edge-Colorings of Graphs
A proper edge-coloring of a graph G by positive integers is called an interval edge-coloring if the colors assigned to the edges incident to any vertex in G are consecutive (i.e., those colors form an interval of integers). The notion of interval edge-colorings was first introduced by Asratian and …
-
Coloring Problems on Graphs and Hypergraphs
An r-edge-coloring of Kn is (r, m)-splittable if V (Kn) can then be r-colored to avoid totally monochromatic m-cliques (introduced by Erdo&huml;s and Gyarfas. We interpret such colorings using a two-round game against an adversary; this relates splittable colorings to classical Ramsey numbers. Let …
-
Edge colorings of graphs on surfaces and star edge colorings of sparse graphs
… dissertation, I present results on two types of edge coloring problems for graphs. For each surface Σ, we define ∆(Σ) = max{∆(G)| G is a class two graph with maximum degree ∆(G) that can be embedded in Σ}. Hence Vizing’s Planar Graph Conjecture can be restated as ∆(Σ) = 5 if Σ is a sphere. For a …
-
Scheduling in computer and communication systems and generalized graph coloring problems
… weighted generalizations of the classical graph coloring problems motivated by scheduling arising in computer and communication systems. The most general problems we attack are called bounded max-vertex/edge-coloring problems and take as input a vertex/edge weighted graph and a bound b. In these …
-
Gallai-Ramsey Number of An 8-Cycle
… the minimum number of vertices n such that any k-edge-coloring of Kn contains either a rainbow (all different colored) triangle or a monochromatic copy of G. In this work, we establish the Gallai-Ramsey number of an 8-cycle for all positive integers.
-
On Ramsey and Gallai-Ramsey numbers of some classes of graphs
… monochromatic clique of a specified size in any edge coloring of a sufficiently large complete graph. This result is commonly known as Ramsey's theorem. The role of Ramsey number is to quantify some specific problems related to Ramsey's theorem. Given a graph H, the Ramsey number R_2(H) is the …
-
Graph Coloring Problems and Group Connectivity
… determined, and our results imply that every 8-edge-connected graph G with independence number at most two admits a mod 5-orientation.;3. Neighbor sum distinguishing total coloring. A proper total k-coloring &phis; of a graph G is a mapping from V(G) ∪ E(G) to {lcub}1,2, . . .,k{rcub} such that …
-
Results on edge-colored graphs and pancyclicity
… many fundamental graph theory concepts such as edge-coloring, routing problems, decomposition problems, and containing cycles of various lengths. The three primary chapters in this thesis address the problems of finding eulerian circuits with additional restrictions, decomposing the edge-colored …
-
Extremal problems in graph theory
We consider generalized graph coloring and other extremal problems in graph theory. We also construct twisted hypercubes of small radius and find the domination number of the Kneser graph $K(n,k)$ when $n\ge{3\over4}k\sp2\pm k,$ depending on whether k is even or odd. The path chromatic number …
-
On Extremal, Algorithmic, and Inferential Problems in Graph Theory
… Alon, Krivelevich, and Sudakov regarding vertex coloring. Our results provide improved bounds in all known cases for which the conjecture holds. Additionally, we introduce a generalized notion of local sparsity and study the independence and chromatic numbers of graphs satisfying this property. …
-
Extremal problems for labelling of graphs and distance in digraphs
… integer D, we determine the minimum number of edges in a digraph with weak diameter at least D, when D = 2, or when the number of vertices of the digraph is very large or small with respect to D. Chapter 3 is based on joint work with Z. Furedi that appears in [26]. In Chapter 4 using Ramsey …
-
Approximation algorithms for multidimensional bin packing
… vector bin packing and weighted bipartite edge coloring. In two-dimensional (2-D) geometric bin packing, we are given a collection of rectangular items to be packed into a minimum number of unit size square bins. Geometric packing has vast applications in cutting stock, vehicle loading, …
-
Multistage interconnection networks : improved routing algorithms and fault tolerance
… well as the Clos and Benes networks. A modified edge coloring algorithm is applied to the regular bipartite multigraph which represents a Clos network. The looping and parallel looping algorithms are examined and a modified Tree-Connected Computer is adopted to execute a bidirectional parallel …
-
Edge-colorings and flows in Class 2 graphs
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 …
Page 1 of 3