• Login
    View Item 
    •   Oxy Scholar Home
    • Mathematics
    • Mathematics URC Student Scholarship
    • View Item
    •   Oxy Scholar Home
    • Mathematics
    • Mathematics URC Student Scholarship
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    N-maximizability of Theta-less Graphs

    Thumbnail
    Author
    Kirov, Radoslav
    Issue
    urc_student
    Date
    2002-01-01 0:00
    Metadata
    Show full item record
    URI
    https://scholar.oxy.edu/handle/20.500.12711/1019
    Abstract
    A graph G is said to be n-maximizable if and only if we get the smallest number of proper colorings when using identical n-lists for all vertices. First we prove that all cycles are n-maximizable for n>=3 (the n=2 case was already known). Then we tried to prove that all theta-less graphs, which are graphs which have at most two independent paths (i.e., with disjoint interiors) between any two vertices, are also n-maximizable. Although we are still working on a proof in the most general case, we can prove it for theta-less graphs build in a certain way. If a graph is n-maximizable, we can add a cycle or path to a vertex of degree 2 and the resulting graph is n-maximizable. Thus we can build chains of cycles. Also we prove that "bouquets" of cycles (a number of cycles sharing one and the same vertex) are n-maximizable.
    Collections
    • Mathematics URC Student Scholarship

    Browse

    All of Oxy ScholarCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsJournal TitleJournal IssueThis CollectionBy Issue DateAuthorsTitlesSubjectsJournal TitleJournal Issue

    My Account

    LoginRegister

    DSpace software copyright © 2002-2021  DuraSpace
    Contact Us | Send Feedback
    DSpace Express is a service operated by 
    Atmire NV