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 15 of 15 for “"Edge-coloring"”.
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
Machine Learning for Unmanned Aerial System (UAS) Networking
… can achieve the max-min throughput globally edge coloring. I leveraged the upper and lower bound to accelerate the optimization of edge coloring.</li> </ol> <p>This dissertation paves a way regarding UAS networking in the integration of CPS and machine learning. The UAS networking can achieve …
-
List coloring in general graphs
… relatively new approaches to the problem of list-coloring graphs. This is a problem that has its roots in classical graph theory, but has developed an entire theory of its own, that uses tools from structural graph theory, probabilistic approaches, as well as heuristic and algorithmic approaches. …
-
On vertex degrees, graph decomposition, and circular chromatic Ramsey number
… isomorphic copies of T. Let T be a tree with m edges. In Chapter 3, we extend the ideas of Snevily and Avgustinovitch to prove the existence of T-decompositions for more 2m-regular graphs and m-regular bipartite graphs. In particular, for r_1,...,r_k with ∑_{i=1}^k r_i=m, we seek sufficient …
-
Distance-1 constrained channel assignment in single radio wireless mesh networks
… assignment problem as a new form of graph edge coloring in which edges at distance one are constrained. I prove that the problem is NP-complete and design an efficient heuristic solution for mesh networks. Second, I design an asynchronous control-channel-based MAC protocol that solves …
-
Approximation algorithms for packing and scheduling problems
… scheduling. The first chapter studies a natural edge-coloring question arising from the problem of scheduling packets through an interconnection network. The theoretical model we consider can be seen as a weighted extension of Konig's theorem that states that the minimum number of colors needed …
-
Locally computing edge orientations
We consider the question of orienting the edges in a graph 𝐺 such that every vertex has bounded out-degree. For graphs of arboricity 𝛼, there is an orientation in which every vertex has out-degree at most 𝛼, and moreover, this is the best possible. We are thus interested in algorithms that can …
-
Games on graphs, visibility representations, and graph colorings
… in G is a set M ⊆ E(G) such that the number of edges of M incident to v is at most f(v) for all v ⊆ V(G). In the f-matching game on a graph G, denoted (G,f), players Max and Min alternately choose edges of G to build an f-matching; the game ends when the chosen edges form a maximal f-matching. …
-
Coloring and covering problems on graphs
… of $V(G)$ such that every two nonincident edges are ``separated'' in some ordering, meaning that both endpoints of one edge appear before both endpoints of the other. We introduce the \emph{fractional separation dimension} $\pi_f(G)$, which is the minimum of $a/b$ such that some $a$ linear …
-
Colorings of sparse graphs and multigraphs
Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms