Show simple item record

dc.contributor.authorBaber, Courtney Leighen_US
dc.date.accessioned2014-03-14T20:39:37Z
dc.date.available2014-03-14T20:39:37Z
dc.date.issued2009-04-30en_US
dc.identifier.otheretd-06082009-155312en_US
dc.identifier.urihttp://hdl.handle.net/10919/33484
dc.description.abstractOne 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Ë os, 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.en_US
dc.publisherVirginia Techen_US
dc.relation.haspartMastersThesis.pdfen_US
dc.rightsI hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to Virginia Tech or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report.en_US
dc.subjectchannel assignment problemen_US
dc.subjectlist coloringen_US
dc.subjectgraphen_US
dc.titleAn Introduction to List Colorings of Graphsen_US
dc.typeThesisen_US
dc.contributor.departmentMathematicsen_US
dc.description.degreeMaster of Scienceen_US
thesis.degree.nameMaster of Scienceen_US
thesis.degree.levelmastersen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineMathematicsen_US
dc.contributor.committeechairBrown, Ezra A.en_US
dc.contributor.committeememberRossi, John F.en_US
dc.contributor.committeememberShimozono, Mark M.en_US
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-06082009-155312/en_US
dc.date.sdate2009-06-08en_US
dc.date.rdate2009-06-11
dc.date.adate2009-06-11en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record