Back to search

West Virginia University

Colouring, covering, reconstruction, and 3-to-1 maps of graphs.

Abstract

dc:description.abstract

There are five chapters in this thesis. In Chapter I, we present some frequently used definitions and notations, and describe the main results in this thesis. In Chapter II, edge-colouring and total colouring of graphs are discussed. The core {dollar}G\\sb{lcub}\\Delta{rcub}{dollar} is the subgraph of G induced by the vertices of maximum degree. If {dollar}G\\sb{lcub}\\Delta{rcub}{dollar} is a forest then Fournier (24) showed that G is Class 1. Therefore if G is Class 2, {dollar}G\\sb{lcub}\\Delta{rcub}{dollar} must contain cycles. A natural question is this: what is the chromatic index of G if {dollar}G\\Delta{dollar} is a union of vertex disjoint cycles? Further information about this question is given in this Chapter. Also we survey several important known results on the total colouring of graphs and prove some new results about total colouring. In Chapter III, we consider the cycle cover problem. The main result in this Chapter is that if G is a 2-connected simple graph of order n (n {dollar}\\ge{dollar} 7) and w is a smallest (1, 2)-eulerian weight of graph G, then {dollar}\\vert E\\sb{lcub}w=even{rcub}\\vert{dollar} {dollar}\\le{dollar} n {dollar}-{dollar} 4, except for a specified family of graphs. A consequence is that, if G admits a nowhere-zero 4-flow and is of order at least 7, except for a specified family of graphs, the total length of a shortest cycle covering is at most {dollar}\\vert V(G)\\vert{dollar} + {dollar}\\vert E(G)\\vert{dollar} {dollar}-{dollar} 4. This result generalizes some previous results. In Chapter IV, we consider the edge-reconstruction of planar graphs. We prove that, if G is a 3-connected planar graph and contains no vertex of degree 4, then G is edge reconstructible. This generalizes a result of J. Lauri. In Chapter V, we study a particular case of the problem of determining for which values of k there is a k-to-1 continuous map from a graph G onto a graph H. We concentrate on the case when H is a cycle, and k = 3, and we characterize all possible connected graphs G.

Degree

thesis:*
Level thesis:degree_level
Thesis

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhao, Cheng

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
West Virginia University
Base URL
researchrepository.wvu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Zhao, Cheng. Colouring, covering, reconstruction, and 3-to-1 maps of graphs.. Thesis thesis, https://doi.org/10.33915/etd.10107