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 19 of 19 for “"forbidden subgraphs"”.

  1. Forbidden subgraphs and 3-colorability

    Classical vertex coloring problems ask for the minimum number of colors needed to color the vertices of a graph, such that adjacent vertices use different colors. Vertex coloring does have quite a few practical applications in communication theory, industry engineering and computer science. Such …

    gatech Repository record for Forbidden subgraphs and 3-colorability (opens in a new tab)

  2. Vertex coloring with forbidden subgraphs

    … characterization of the line graphs in terms of forbidden subgraphs. By using {\it clique-width} and {\it perfect graphs} theory, we show that ($claw$,$4K_1$,$hole$-$twin$)-free graphs and ($4K_1$,$hole$-$twin$,$5$-$wheel$)-free graphs are either perfect or have bounded clique-width. And thus the …

    wilfrid-laurier Repository record for Vertex coloring with forbidden subgraphs (opens in a new tab) Download PDF for Vertex coloring with forbidden subgraphs (opens in a new tab)

  3. Extremal problems involving forbidden subgraphs

    … thesis, we study extremal problems involving forbidden subgraphs. We are interested in extremal problems over a family of graphs or over a family of hypergraphs. In Chapter 2, we consider improper coloring of graphs without short cycles. We find how sparse an improperly critical graph can be …

    uiuc Repository record for Extremal problems involving forbidden subgraphs (opens in a new tab)

  4. Extremal properties of degree sequences: potential functions for subgraphs and forbidden subgraphs

    … number of edges, but they may not have the same subgraphs. In 1991 Erdős, Jacobson, and Lehel, introduced the concept of the `potential function' of a graph H: the least number of edges in a graph on n vertices for which some other graph with the same degree sequence contains a copy of a fixed …

    manitoba Repository record for Extremal properties of degree sequences: potential functions for subgraphs and forbidden subgraphs (opens in a new tab)

  5. The Minimum Rank Problem Over Finite Fields

    … bound for the number of vertices in a minimal forbidden subgraph for the graphs having minimum rank at most 3 over the finite field of order 2. We also list all 62 such minimal forbidden subgraphs and show that many of these are minimal forbidden subgraphs for any field. Our second main result …

    byu Repository record for The Minimum Rank Problem Over Finite Fields (opens in a new tab) Download PDF for The Minimum Rank Problem Over Finite Fields (opens in a new tab)

  6. Chordality of digraphs, signed graphs, and signed bigraphs

    … enjoy beautiful characterizations, in terms of forbidden subgraphs, vertex or edge orderings, and tree-like representations. A digraph analogue of chordal graphs was introduced by Haskins and Rose. Unfortunately, a forbidden subdigraph characterization of chordal digraphs is not known and …

    uvic Repository record for Chordality of digraphs, signed graphs, and signed bigraphs (opens in a new tab)

  7. Generalised disk graphs

    … to characterize the graphs and find forbidden subgraphs. We find that in the one dimensional case, we are able to order the vertices which allows us to restrict the structure of subgraphs in relation to the graphs order. We show that the graph $K_{2,3}$ is forbidden in the …

    reykjavik Repository record for Generalised disk graphs (opens in a new tab)

  8. Efficient algorithms in quantum query complexity

    … that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity Theta(n^{3/2}) and those that do have such a characterization can be solved strictly faster, with o(n^{3/2}) queries. Our lower bound is based on a detailed analysis of the structure of …

    waterloo Repository record for Efficient algorithms in quantum query complexity (opens in a new tab)

  9. A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes

    … In this paper we show that if each H_i has a forbidden subgraph characterization then the direct sum and join of these H_i also have forbidden subgraph characterizations. We provide various results which in many cases allow us to exactly determine the minimal forbidden subgraphs for such …

    byu Repository record for A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes (opens in a new tab) Download PDF for A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes (opens in a new tab)

  10. On chordal digraphs and semi-strict chordal digraphs

    … to elegant characterizations in terms of forbidden subgraphs, subtree representations, vertex orderings, and to linear time recognition algorithms. Haskins and Rose introduced the class of chordal digraphs as a digraph analogue of chordal graphs. Chordal digraphs can be defined in terms of …

    uvic Repository record for On chordal digraphs and semi-strict chordal digraphs (opens in a new tab)

  11. Extremal problems on graphs, directed graphs and hypergraphs

    … of graphs and directed graphs with some forbidden subgraphs. We answer a question of Cherlin by finding the typical structure of triangle-free oriented graphs. Moreover, our results generalise to forbidden transitive tournaments and forbidden oriented cycles of any order, and also apply …

    birmingham Download PDF for Extremal problems on graphs, directed graphs and hypergraphs (opens in a new tab)

  12. Forbidden substructures: induced subgraphs, Ramsey games, and sparse hypergraphs

    … in extremal combinatorics with respect to forbidden induced subgraphs, forbidden colored subgraphs, and forbidden subgraphs. In Chapter 2, we determine exactly which graphs H have the property that almost every H-free graph has a vertex partition into k cliques and independent sets and …

    uiuc Repository record for Forbidden substructures: induced subgraphs, Ramsey games, and sparse hypergraphs (opens in a new tab)

  13. Uniqueness and Complexity in Generalised Colouring

    … include: · a characterisation of the minimal forbidden subgraphs of a hereditary property in terms of its minimal forbidden induced-subgraphs, and <i>vice versa</i>; · extensions of Mihók's construction of uniquely colourable graphs, and Scheinerman's characterisations of compositivity, to …

    waterloo Repository record for Uniqueness and Complexity in Generalised Colouring (opens in a new tab)

  14. Distance-preserving graphs

    … this end, we carefully examine the role of "forbidden" subgraphs. We discuss our observations, and provide some conjectures which we computationally verified for small values of n. We say that a distance-preserving graph is sequentially distance-preserving if each subgraph in the set of …

    msu Repository record for Distance-preserving graphs (opens in a new tab)

  15. Forbidding and Enforcing of Formal Languages, Graphs, and Partially Ordered Sets

    … new classes of languages (fe-families) based on forbidden subwords and enforced words. This paper considers a metric on languages and proves that the metric space obtained is homeomorphic to the Cantor space. This work studies Chomsky classes of families as subspaces and shows they are neither …

    usf Repository record for Forbidding and Enforcing of Formal Languages, Graphs, and Partially Ordered Sets (opens in a new tab)

  16. Results on edge-colored graphs and pancyclicity

    … graph with additional structure contains certain subgraphs, particularly circuits, cycles, or trees. The specific problems and presented results include a blend of many fundamental graph theory concepts such as edge-coloring, routing problems, decomposition problems, and containing cycles of …

    nebraska Repository record for Results on edge-colored graphs and pancyclicity (opens in a new tab)

  17. Extremal problems in disjoint cycles and graph saturation

    … conditions for the existence of particular subgraphs in a graph, and variations on graph saturation. Determining whether a graph contains a certain subgraph is a computationally difficult problem; as such, sufficient conditions for the existence of a given subgraph are prized. In Chapter 2, …

    uiuc Repository record for Extremal problems in disjoint cycles and graph saturation (opens in a new tab)

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

    … the non-representable cases, we identify induced subgraphs whose neighbourhoods are not comparability graphs, or which lie in a known family of forbidden subgraphs of Hauser. We then refine these results to show that within this subfamily, word-representability is in fact equivalent to being a …

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

  19. Power Graphs of Quasigroups

    We investigate power graphs of quasigroups. The power graph of a quasigroup takes the elements of the quasigroup as its vertices, and there is an edge from one element to a second distinct element when the second is a left power of the first. We first compute the power graphs of small quasigroups …

    usf Repository record for Power Graphs of Quasigroups (opens in a new tab)