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 20 of 163 for “"Chromatic Number"”.

  1. The Local Chromatic Number

    A graph vertex colouring is called k-local if the number of colours used in the closed neighbourhood of each vertex is at most k. The local chromatic number of a graph is the smallest k for which the graph has a proper k-local colouring. So unlike the chromatic number which is the minimum total …

    waterloo Repository record for The Local Chromatic Number (opens in a new tab)

  2. Chromatic Number of Random Signed Graphs

    … Bollobas's classical method and result about the chromatic number of random graphs chi(G(n,p)) ~ n/log_b(n) (for p constant, b=1/(1-p)) to the chromatic number of random signed graphs to obtain chi(G(n,p,q)) ~ n/log_b(n) (for p constant, b=1/(1-p), q=o(1)). We also give a sufficient bound on q …

    waterloo Repository record for Chromatic Number of Random Signed Graphs (opens in a new tab)

  3. The circular chromatic number of hypergraphs

    A generalization of the circular chromatic number to hypergraphs is devel-oped. Circular colourings of graphs and hypergraphs are first discussed and it is shown that the circular chromatic number of a graph is the same regard-less of whether the hypergraph or graph definition is used. After …

    uvic Repository record for The circular chromatic number of hypergraphs (opens in a new tab)

  4. Two graph classes with bounded chromatic number

    A class of graphs is said to be $\chi$-bounded with binding function $f$ if for every such graph $G$, it satisfies $\chi(G) \leq f(\omega(G)$, and polynomially $\chi$-bounded if $f$ is a polynomial. It was conjectured that chair-free graphs are perfectly divisible, and hence admit a quadratic …

    gatech Repository record for Two graph classes with bounded chromatic number (opens in a new tab)

  5. Local properties of graphs with large chromatic number

    … the local properties of graphs with large chromatic number in hereditary classes of graphs. We construct intersection graphs of axis-aligned boxes and of lines in $\mathbb{R}^3$ that have arbitrarily large girth and chromatic number. We also prove that the maximum chromatic number of a …

    waterloo Repository record for Local properties of graphs with large chromatic number (opens in a new tab)

  6. The Packing Chromatic Number of Random d-regular Graphs

    … k of a packing coloring is called the packing chromatic number of G, denoted by Xp(G). Let Gn,d denote the random d-regular graph on n vertices. In this thesis, we show that for any fixed d >= 4, there exists a positive constant cd such that P(Xp(Gn,d) >=cdn) = 1 − on(1).

    south-carolina Repository record for The Packing Chromatic Number of Random d-regular Graphs (opens in a new tab)

  7. Solving Chromatic Number with Quantum Search and Quantum Counting

    … a novel quantum algorithm that solves the Chromatic Number problem. Complexity analysis of this algorithm revealed a run time of O(2n/2n2(log2n)2). This is an improvement over the best known algorithm, with a run time of 2nnO(1) [1]. This algorithm uses the Quantum Search algorithm (often …

    calpoly Repository record for Solving Chromatic Number with Quantum Search and Quantum Counting (opens in a new tab)

  8. On List-Coloring and the Sum List Chromatic Number of Graphs.

    … a specialization of list coloring, the sum list chromatic number is explored in detail. Ultimately, the thesis is designed to motivate the discussion of coloring problems and, hopefully, interest the reader in the branch of coloring problems in graph theory.

    vcu Repository record for On List-Coloring and the Sum List Chromatic Number of Graphs. (opens in a new tab)

  9. The difficulty of approximating the chromatic number for random composite graphs

    "Combinatorial Optimization is an important class of techniques for solving Combinatorial Problems. Many practical problems are Combinatorial Problems, such as the Traveling Salesman Problem (TSP) and Composite Graph Coloring Problem (CGCP). Unfortunately, both of these problems are ��P-complete …

    must-thes Repository record for The difficulty of approximating the chromatic number for random composite graphs (opens in a new tab)

  10. Algorithms and probabilistic bounds for the chromatic number of random composite graphs

    … each vertex is a positive integer called its chromaticity. The chromaticity of a vertex specifies the number of consecutive colors which must be assigned to it. An exact algorithm for solving the CGCP is presented. The algorithm is a generalization of the vertex-sequential with dynamic …

    must-thes Repository record for Algorithms and probabilistic bounds for the chromatic number of random composite graphs (opens in a new tab)

  11. Topological Approaches to Chromatic Number and Box Complex Analysis of Partition Graphs

    Determining the chromatic number of the partition graph P(33) poses a considerable challenge. We can bound it to 4 ≤ χ(P(33)) ≤ 6, with exhaustive search confirming χ(P(33)) = 6. A potential mathematical proof strategy for this equality involves identifying a Z2-invariant S4 with non-trivial …

    ottawa-retro Repository record for Topological Approaches to Chromatic Number and Box Complex Analysis of Partition Graphs (opens in a new tab)

  12. Approximating the chromatic number of an arbitrary graph using a supergraph heuristic

    … among others. Graph coloring with the minimum number of colors is in general an NP-complete problem. However, there are several classes of graphs for which coloring is a polynomial-time problem. One such class is the chordal graphs. This thesis deals with an experimental algorithm to …

    nps Repository record for Approximating the chromatic number of an arbitrary graph using a supergraph heuristic (opens in a new tab)

  13. On Finding Large Cliques when the Chromatic Number is close to the Maximum Degree

    We prove that every graph G with chromatic number χ(G) = ∆(G) − 1 and ∆(G) ≥ 66 contains a clique of size ∆(G) − 17. Our proof closely parallels a proof from Cranston and Rabern, who showed that graphs with χ = ∆ and ∆ ≥ 13 contain a clique of size ∆ − 3. Their result is the best currently known …

    waterloo Repository record for On Finding Large Cliques when the Chromatic Number is close to the Maximum Degree (opens in a new tab)

  14. On the relation among the maximum degree, the chromatic number and the clique number

    … among the maximum degree $\Delta(G)$, the chromatic number $\chi(G)$ and the clique number $\omega(G)$ of a graph $G$ by proving results related to the Borodin-Kostochka Conjecture and Reed's Conjecture, which are two long-standing conjectures on this subject. The Borodin-Kostochka …

    waterloo Repository record for On the relation among the maximum degree, the chromatic number and the clique number (opens in a new tab)

  15. On the chromatic number of the <em>AO</em>(2, <em>k </em>, <em>k</em>-1) graphs.

    … overlap graphs. In this work we determine the chromatic number for a special case of these graphs.We define the alphabet overlap graph by G = AO(a, k, t, where a, k and t are positive integers such that 0 ≤ t ≤ k. The vertex set of G is the set of all k-letter sequences over an alphabet of size …

    etsu Repository record for On the chromatic number of the <em>AO</em>(2, <em>k </em>, <em>k</em>-1) graphs. (opens in a new tab) Download PDF for On the chromatic number of the <em>AO</em>(2, <em>k </em>, <em>k</em>-1) graphs. (opens in a new tab)

  16. Two Questions about Properties of Large Graphs: On Generalized Turán Numbers and the Chromatic Number of Random Lifts

    … theorem of Turán that states that the maximum number of edges in a clique-free graph is uniquely obtained by a balanced complete r-partite graph. Following Alon and Shikhelman, instead of counting edges while forbidding cliques, I count copies of a target graph T while forbidding copies of F. I …

    nebraska Repository record for Two Questions about Properties of Large Graphs: On Generalized Turán Numbers and the Chromatic Number of Random Lifts (opens in a new tab)

  17. On the Attainability of Upper Bounds for the Circular Chromatic Number of <em>K</em><sub>4</sub>-Minor-Free Graphs.

    … xy is an edge of G. We say that the circular chromatic number of G, denoted χc(G), is equal to the smallest k/d where a k/d -coloring exists. In [6], Pan and Zhu have given a function μ(g) that gives an upper bound for the circular-chromatic number for every K4-minor-free graph Gg of odd girth …

    etsu Repository record for On the Attainability of Upper Bounds for the Circular Chromatic Number of <em>K</em><sub>4</sub>-Minor-Free Graphs. (opens in a new tab) Download PDF for On the Attainability of Upper Bounds for the Circular Chromatic Number of <em>K</em><sub>4</sub>-Minor-Free Graphs. (opens in a new tab)

  18. Homomorphisms of (j, k)-mixed graphs

    … graph to a target with m vertices. The (j, k)−chromatic number of a (j, k)−mixed graph is the least m such that an m−colouring exists. When (j, k) = (0, 1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring. Similarly, when (j, k) …

    uvic Repository record for Homomorphisms of (j, k)-mixed graphs (opens in a new tab)

Page 1 of 9