Date of Graduation
1998
Document Type
Dissertation/Thesis
Abstract
Given a graph G, for each {dollar}v\\in V(G){dollar} let L(v) be a list assignment to G. The well-known choice number c(G) (or sometimes referred to as list chromatic number of G) is the least integer j such that if {dollar}\\vert L(v)\\vert\\ge j{dollar} for all {dollar}v\\in V(G){dollar} then G has a proper vertex coloring {dollar}\\phi{dollar} with {dollar}\\phi(v)\\in L(v)\\ (\\forall v\\in V(G)).{dollar} The Hall number h(G) is defined like the choice number is defined, except that an extra non-triviality condition, called Hall's condition, must be satisfied. The edge-analogue of the Hall number is called the Hall index and is denoted {dollar}h\\sp\\prime(G).{dollar} If the stock of colors from which L(v) is selected to a set of size k, then the analogues are called k-restricted, or restricted, Hall parameters, and are denoted {dollar}h\\sb{lcub}k{rcub}(G){dollar} and {dollar}h\\sp\\prime\\sb{lcub}k{rcub}(G).{dollar} This dissertation resolves many of the hitherto unresolved questions in the current literature concerning Hall parameters. We also determine or closely bound {dollar}h\\sp\\prime(K\\sb{lcub}n{rcub}),\\ h\\sp\\prime(K\\sb{lcub}m,n{rcub}){dollar} and {dollar}h\\sp\\prime\\sb{lcub}k{rcub}(K\\sb{lcub}m,n{rcub}).{dollar} We show in particular that there are examples of graphs G with {dollar}h\\sp\\prime(G)-h\\sp\\prime(G-e)>1.{dollar} We show that there are families of graphs G each containing an induced subgraph H with {dollar}h\\sb{lcub}k{rcub}(G)
Recommended Citation
Cropper, Matthew M., "Hall's condition and list coloring." (1998). Graduate Theses, Dissertations, and Problem Reports. 8687.
https://researchrepository.wvu.edu/etd/8687