Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 8 of 8 for “"Comparability Graphs"”.

  1. Generalizations of comparability graphs

    … been studied extensively. In graph theory, a comparability graph is an undirected graph which connects all comparable elements in a partial order. A transitive orientation is an assignment of direction to every edge so that the resulting directed graph is transitive. A graph is transitive if …

    colostate Repository record for Generalizations of comparability graphs (opens in a new tab)

  2. Simultaneous Graph Representation Problems

    Many graphs arising in practice can be represented in a concise and intuitive way that conveys their structure. For example: A planar graph can be represented in the plane with points for vertices and non-crossing curves for edges. An interval graph can be represented on the real line with …

    waterloo Repository record for Simultaneous Graph Representation Problems (opens in a new tab)

  3. Coloring clique hypergraphs

    … of CH(G). We prove that the clique hypergraphs of chordal and comparability graphs are bicolorable and that the clique hypergraphs of circular-arc graphs are 3-colorable. Our main result is the characterization of (W, 2)-extendibility for chordal graphs in the case when W=2 .

    wvu Repository record for Coloring clique hypergraphs (opens in a new tab)

  4. On approximating transitivity and tractability of graphs

    … are NP-hard. But, there exists some families of graphs, called perfect graphs, where these problems become tractable. One particular class of perfect graphs are the the underlying undirected graphs of transitive digraphs- called comparability graphs. We define a new parameter β to approximate the …

    colostate Repository record for On approximating transitivity and tractability of graphs (opens in a new tab)

  5. The computational complexity of edge colouring restricted graphs

    … complexity of edge colouring restricted graphs. Previous work has established that the chromatic index problem restricted to k­-regular graphs for any fixed k-3 remains NP-complete, whereas the problem restricted to bipartite graphs and partial k-trees for fixed k is in P. We show that …

    uvic Repository record for The computational complexity of edge colouring restricted graphs (opens in a new tab)

  6. Pattern sequencing models in cutting stock problems

    … to use the rich theory that exists in interval graphs in order to create a model based on the completion of a graph with edges. The structure of this type of graphs admits a linear ordering of the vertices that de nes an ordering of the stacks, and consequently decides a sequence for the cutting …

    minho-thes Repository record for Pattern sequencing models in cutting stock problems (opens in a new tab)

  7. On word-representability of Apollonian graphs and 1-11-representability of graphs

    … While the class of word-representable graphs is rich containing all 3-colourable graphs, all comparability graphs, and all circle graphs, not every graph is word-representable, and characterising word-representable planar graphs remains a long-standing open problem. This thesis is …

    strathclyde Repository record for On word-representability of Apollonian graphs and 1-11-representability of graphs (opens in a new tab)

  8. Assortment and Pricing Optimisation under non-conventional customer choice models

    … under the 2SLM and independent sets in comparability graphs. The third and final contribution is an in-depth study of the pricing problem under the 2SLM. We first note that changes in prices should be reflected in the dominance relation if the differences between the resulting …

    anu Repository record for Assortment and Pricing Optimisation under non-conventional customer choice models (opens in a new tab)