• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • 1
  • 1
  • Tagged with
  • 3
  • 3
  • 3
  • 3
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Knotenfärbungen mit Abstandsbedingungen

Kohl, Anja 16 December 2009 (has links) (PDF)
Knotenfärbungen mit Abstandsbedingungen sind graphentheoretische Konzepte, motiviert durch das praktische Problem der Frequenzzuweisung in Mobilfunknetzen. In der Arbeit werden verschiedene Varianten solcher Färbungen vorgestellt. Für (Listen-)Färbungen mit einer beliebigen Anzahl r von Abstandsbedingungen werden allgemeine Eigenschaften und Schranken für die benötigte Anzahl von Farben bewiesen. Anschließend wird der Spezialfall r=2 behandelt. Färbungen mit zwei Abstandsbedingungen - die sogenannten L(d,s)-Labellings - werden für eine Reihe von Graphenklassen untersucht, u.a. für reguläre Parkettierungen, Weg- und Kreispotenzen und Graphen mit Durchmesser 2. Die Listenversion dieser Färbungen - die sogenannten L(d,s)-List Labellings - werden für Wege, Sterne, Kreise und Kakteen betrachtet. Ferner werden Untersuchungen zum Zusammenhang von L(2,1)-Labellings und L(2,1)-List Labellings bei speziellen Bäumen durchgeführt.
2

Knotenfärbungen mit Abstandsbedingungen

Kohl, Anja 30 August 2006 (has links)
Knotenfärbungen mit Abstandsbedingungen sind graphentheoretische Konzepte, motiviert durch das praktische Problem der Frequenzzuweisung in Mobilfunknetzen. In der Arbeit werden verschiedene Varianten solcher Färbungen vorgestellt. Für (Listen-)Färbungen mit einer beliebigen Anzahl r von Abstandsbedingungen werden allgemeine Eigenschaften und Schranken für die benötigte Anzahl von Farben bewiesen. Anschließend wird der Spezialfall r=2 behandelt. Färbungen mit zwei Abstandsbedingungen - die sogenannten L(d,s)-Labellings - werden für eine Reihe von Graphenklassen untersucht, u.a. für reguläre Parkettierungen, Weg- und Kreispotenzen und Graphen mit Durchmesser 2. Die Listenversion dieser Färbungen - die sogenannten L(d,s)-List Labellings - werden für Wege, Sterne, Kreise und Kakteen betrachtet. Ferner werden Untersuchungen zum Zusammenhang von L(2,1)-Labellings und L(2,1)-List Labellings bei speziellen Bäumen durchgeführt.
3

Colourings of $P_5$-free graphs

Geißer, Maximilian 31 May 2022 (has links)
For a set of graphs H, we call a graph G H-free if G-S is non-isomorphic to H for each S⊆V(G) and each H∈H. Let f_H^* ∶N_(>0)↦N_(>0 )be the optimal χ-binding function of the class of H-free graphs, that is, f_H^* (ω)=max⁡{χ(G): ω(G)=ω,G is H-free} where χ(G),ω(G) denote the chromatic number and clique number of G, respectively. In this thesis, we mostly determine optimal χ-binding functions for subclasses of P_5-free graphs, where P_5 denotes the path on 5 vertices. For multiple subclasses we are able to determine them exactly and for others we prove the right order of magnitude. To achieve those results we prove structural results for the graph classes and determine colourings. We sometimes obtain those results by researching the prime graphs and combining the two decomposition methods by homogeneous sets and clique-separators. Additionally, we use the Strong Perfect Graph Theorem and analyse the neighbourhood of holes. For some of these subclasses we characterise all graphs G with χ(G)>χ(G-\{u\}), for each u∈V(G) and use those to determine the function.

Page generated in 0.0724 seconds