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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:79196 |
| Date | 31 May 2022 |
| Creators | Geißer, Maximilian |
| Contributors | Schiermeyer, Ingo, Randerath, Hubert, Technische Universität Bergakademie Freiberg |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 10.48550/arXiv.2005.02250, 10.1007/978-3-030-83823-2_49 |
Page generated in 0.0022 seconds