阿根廷vs墨西哥竞猜
 library logo
    • login
    view item 
    •   knowledge commons home
    • electronic theses and dissertations
    • retrospective theses
    • view item
    •   knowledge commons home
    • electronic theses and dissertations
    • retrospective theses
    • view item
    javascript is disabled for your browser. some features of this site may not work without it.
    quick search

    browse

    all of knowledge commonscommunities & collectionsby issue dateauthorstitlessubjectsdisciplineadvisorcommittee memberthis collectionby issue dateauthorstitlessubjectsdisciplineadvisorcommittee member

    my account

    login

    on the perfect orderability of unions of two graphs

    thumbnail
    view/open
    tux1996m-1b.pdf (2.883mb)
    date
    1996
    author
    tu, xiaodan
    metadata
    show full item record
    abstract
    a graph g is perfectly orderable if it admits an order < on its vertices such that the sequential coloring algorithm delivers an optimum coloring on each induced subgraph (h, <) of (g, <). a graph is a threshold graph if it contains no p4 , 2k2 or c4 as induced subgraph. a theorem of chvatal, hoang, mahadev and de werra states that a graph is perfectly orderable if it can be written as the union of two threshold graphs. in this thesis, we investigate possible generalizations of the above theorem. we conjecture that if g is the union of two graphs g1 and g2 then g is perfectly orderable whenever (i) g1 and g2 are both p4 -free and 2k2-free, or (ii) g1 is p4-free, 2k2-free and g2 is p4 -free, c4 -free. we show that the complement of the chordless cycle with at least five vertices cannot be a counter-example to our conjecture and we prove, jointly with hoang, a special case of (i): if g1 and g2 are two edge disjoint graphs that are p4 -free and 2k2 -free then the union of g1 and g2 is perfectly orderable.
    uri
    http://knowledgecommons.lakeheadu.ca/handle/2453/2445
    collections
    • retrospective theses [1604]

    阿根廷vs墨西哥竞猜 library
    contact us | send feedback

     

     


    阿根廷vs墨西哥竞猜 library
    contact us | send feedback