{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/33484"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/33484","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"An Introduction to List Colorings of Graphs","abstract":"One of the most popular and useful areas of graph theory is graph colorings. A graph coloring is an assignment of integers to the vertices of a graph so that no two adjacent vertices are assigned the same integer. This problem frequently arises in scheduling and channel assignment applications. A list coloring of a graph is an assignment of integers to the vertices of a graph as before with the restriction that the integers must come from specific lists of available colors at each vertex. For a physical application of this problem, consider a wireless network. Due to hardware restrictions, each radio has a limited set of frequencies through which it can communicate, and radios within a certain distance of each other cannot operate on the same frequency without interfering. We model this problem as a graph by representing the wireless radios by vertices and assigning a list to each vertex according to its available frequencies. We then seek a coloring of the graph from these lists. In this thesis, we give an overview of the last thirty years of research in list colorings. We begin with an introduction of the list coloring problem, as defined by Erdös, Rubin, and Taylor in [6]. We continue with a study of variations of the problem, including cases when all the lists have the same length and cases when we allow different lengths. We will briefly mention edge colorings and overview some restricted list colors such as game colorings and L(p, q)-labelings before concluding with a list of open questions.","abstract_html":"One of the most popular and useful areas of graph theory is graph colorings. A graph coloring is an assignment of integers to the vertices of a graph so that no two adjacent vertices are assigned the same integer. This problem frequently arises in scheduling and channel assignment applications. A list coloring of a graph is an assignment of integers to the vertices of a graph as before with the restriction that the integers must come from specific lists of available colors at each vertex. For a physical application of this problem, consider a wireless network. Due to hardware restrictions, each radio has a limited set of frequencies through which it can communicate, and radios within a certain distance of each other cannot operate on the same frequency without interfering. We model this problem as a graph by representing the wireless radios by vertices and assigning a list to each vertex according to its available frequencies. We then seek a coloring of the graph from these lists. In this thesis, we give an overview of the last thirty years of research in list colorings. We begin with an introduction of the list coloring problem, as defined by Erdös, Rubin, and Taylor in [6]. We continue with a study of variations of the problem, including cases when all the lists have the same length and cases when we allow different lengths. We will briefly mention edge colorings and overview some restricted list colors such as game colorings and L(p, q)-labelings before concluding with a list of open questions.","abstract_has_math":false,"creators":["Baber, Courtney Leigh"],"institution":"Virginia Tech","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Mathematics","degree_department":"Mathematics","school":null,"contributors":[],"advisors":[],"committee_chairs":["Brown, Ezra A."],"committee_members":["Rossi, John F.","Shimozono, Mark M."],"year":2009,"date_issued":"2009-04-30","date_published":"2009-04-30","updated_at":"2026-07-22T22:19:13Z","subjects":["channel assignment problem","list coloring","graph"],"languages":[],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-06082009-155312"],"render_values":[{"text":"etd-06082009-155312","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10919/33484","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeechair","label":"Committee Chair","values":["Brown, Ezra A."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Rossi, John F.","Shimozono, Mark M."]},{"key":"dc:contributor.department","label":"Department","values":["Mathematics"]},{"key":"dc:creator","label":"Author","values":["Baber, Courtney Leigh"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-03-14T20:39:37Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-03-14T20:39:37Z","2009-06-11"]},{"key":"dc:date.issued","label":"Date","values":["2009-04-30"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["channel assignment problem","list coloring","graph"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-06082009-155312"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/33484"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["One of the most popular and useful areas of graph theory is graph colorings. A graph coloring is an assignment of integers to the vertices of a graph so that no two adjacent vertices are assigned the same integer. This problem frequently arises in scheduling and channel assignment applications. A list coloring of a graph is an assignment of integers to the vertices of a graph as before with the restriction that the integers must come from specific lists of available colors at each vertex. For a physical application of this problem, consider a wireless network. Due to hardware restrictions, each radio has a limited set of frequencies through which it can communicate, and radios within a certain distance of each other cannot operate on the same frequency without interfering. We model this problem as a graph by representing the wireless radios by vertices and assigning a list to each vertex according to its available frequencies. We then seek a coloring of the graph from these lists. In this thesis, we give an overview of the last thirty years of research in list colorings. We begin with an introduction of the list coloring problem, as defined by Erdös, Rubin, and Taylor in [6]. We continue with a study of variations of the problem, including cases when all the lists have the same length and cases when we allow different lengths. We will briefly mention edge colorings and overview some restricted list colors such as game colorings and L(p, q)-labelings before concluding with a list of open questions."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science"]},{"key":"dc:title","label":"Title","values":["An Introduction to List Colorings of Graphs"]}]}],"canonical_facts":{"dc:contributor.committeechair":["Brown, Ezra A."],"dc:contributor.committeemember":["Rossi, John F.","Shimozono, Mark M."],"dc:contributor.department":["Mathematics"],"dc:creator":["Baber, Courtney Leigh"],"dc:date.accessioned":["2014-03-14T20:39:37Z"],"dc:date.available":["2014-03-14T20:39:37Z","2009-06-11"],"dc:date.issued":["2009-04-30"],"dc:description.abstract":["One of the most popular and useful areas of graph theory is graph colorings. A graph coloring is an assignment of integers to the vertices of a graph so that no two adjacent vertices are assigned the same integer. This problem frequently arises in scheduling and channel assignment applications. A list coloring of a graph is an assignment of integers to the vertices of a graph as before with the restriction that the integers must come from specific lists of available colors at each vertex. For a physical application of this problem, consider a wireless network. Due to hardware restrictions, each radio has a limited set of frequencies through which it can communicate, and radios within a certain distance of each other cannot operate on the same frequency without interfering. We model this problem as a graph by representing the wireless radios by vertices and assigning a list to each vertex according to its available frequencies. We then seek a coloring of the graph from these lists. In this thesis, we give an overview of the last thirty years of research in list colorings. We begin with an introduction of the list coloring problem, as defined by Erdös, Rubin, and Taylor in [6]. We continue with a study of variations of the problem, including cases when all the lists have the same length and cases when we allow different lengths. We will briefly mention edge colorings and overview some restricted list colors such as game colorings and L(p, q)-labelings before concluding with a list of open questions."],"dc:description.degree":["Master of Science"],"dc:identifier.other":["etd-06082009-155312"],"dc:identifier.uri":["http://hdl.handle.net/10919/33484"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["channel assignment problem","list coloring","graph"],"dc:title":["An Introduction to List Colorings of Graphs"],"dc:type":["Thesis"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:13Z"}