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 18 of 18 for “"chromatic polynomial"”.
-
Quivers Representations, Robinson-Schensted Correspondence and Stanley's Symmetrized Chromatic Polynomial
… correspondence and Stanley’s symmetrized chromatic polynomial. In quivers representations, we learned our old result for proving Lee-Lee conjecture about geometry of real Schur roots which played an important role in both quivers representations and cluster algebras. Next we learn some new …
-
Polynomials associated with graph coloring and orientations
… contexts. Firstly, we generalize Stanley's chromatic symmetric function using the k-balanced colorings of Pretzel to create a new graph invariant. We show that in fact this invariant is a quasisymmetric function which has a positive expansion in the fundamental basis. We also define a graph …
-
Building fences around the chromatic coefficients.
… do not allow us to completely predict all chromatic polynomials, they do serve to severely limit the form of polynomials considered to be candidates for the chromatic polynomial of some graph.
-
Symmetries
… are investigated. The invariance of the chromatic polynomial in the rotor effect is disproved. New invariance results are obtained. It is shown that given any integer k > 2 , almost every finite group acts as the regular full automorphism group of some k-uniform hypergraph. Permutation …
-
Results on Chromatic Polynomials Inspired by a Correlation Inequality of G.E. Farr
… We restate Farr's work in terms of the bivariate chromatic polynomial of Dohmen, Poenitz, Tittman and give a simple, self-contained proof of Farr's inequality using a basic combinatorial approach. We attempt to prove Farr's conjecture through methods in stable polynomials and computational …
-
Vertex-Weighted Generalizations Of Chromatic Symmetric Functions
… by Richard Stanley in the early 1990s, the chromatic symmetric func- tion X G of a graph G enumerates for each integer partition λ of |V (G)| the number of proper colorings of G that partition V (G) into stable sets of sizes equal to the parts of λ. Thus, X G is a refinement of the …
-
Improving the capacity of radio spectrum: exploration of the acyclic orientations of a graph
… a(G). This is just the evaluation of the chromatic polynomial of the graph χ(G; λ) at λ = -1. Calculating (and even approximating) the chromatic polynomial is known to be #P-hard, but it is unknown whether or not the approximation at the value -1 is. There are two key contributions in this …
-
Graph polynomials and their representations
Graph polynomials are polynomials associated to graphs that encode the number of subgraphs with given properties. We list different frameworks used to define graph polynomials in the literature. We present the edge elimination polynomial and introduce several graph polynomials equivalent to it. …
-
Counting Subtrees Using the Chromatic Symmetric Function
In 1995 Richard Stanley defined the chromatic symmetric function as a generalization of the chromatic polynomial. In the same paper Stanley gave a expansion of the chromatic symmetric function in the power-sum basis for symmetric functions. This expansion is cancellation-free when the graph is …
-
Chromatic polynomials of mixed graphs
… λ–colourings of G, denoted fo(G,λ), is a polynomial in λ. We call fo(G,λ) the mixed-chromatic polynomial of G. In this thesis we will first present the basic theory of the mixed-chromatic poly-nomial. This theory will include computational tools and results concerning the coefficients of …
-
Caterpillars, ribbons, and the chromatic symmetric function
For every n-vertex tree T, it is known that the chromatic polynomial x(T, k) is equal to k(k — l )ⁿ⁻¹. It is known that the function in noncommuting variables, Y[sub G](x), distinguishes all simple graphs. In the midground, the question of whether or not the chromatic symmetric function X[sub G](x) …
-
Ham sandwiches, staircases and counting polynomials
… Hilbert Functions. Steingrímsson showed that the chromatic polynomial of a graph, shifted by one, is the Hilbert function of a relative Stanley-Reisner ideal. Dall and myself show that the modluar flow and tension polynomials as well as the integer valued flow and tension polynomials are Hilbert …
-
Some Connections Between Complex Dynamics and Statistical Mechanics
… to any finite simple graph $\Gamma$ is the {\em chromatic polynomial} $\P_\Gamma(q)$ whose complex zeros are called the {\em chromatic zeros} of $\Gamma$. A hierarchical lattice is a sequence of finite simple graphs $\{\Gamma_n\}_{n=0}^\infty$ built recursively using a substitution rule expressed …
-
On the chromatic symmetric functions of trees
The chromatic symmetric function (CSF) of a graph, introduced by Richard Stanley in 1995, is a symmetric function generalization of the chromatic polynomial which enumerates proper colorings by the number of uses of each color. We attack a long-standing open question of Stanley that asks whether …
-
Lattice Polytopes - Applications and Properties
… matrix. We describe an explicit formula for the chromatic polynomial of the product with a path graph. Moreover, we describe the asymptotic behavior in the case of the product with a cycle graph. In Chapter 4, we examine and fully characterize the level property of order polytopes, where …
-
Efficient Computation of Chromatic and Flow Polynomials
This thesis surveys chromatic and flow polynomials, and presents new efficient methods to compute these polynomials on specific families of graphs. The chromatic and flow polynomials of a graph count the number of ways to color and assign flow to the graph; they also contain other important …
-
The complexity of graph polynomials
<p>This thesis examines graph polynomials and particularly their complexity. We give short proofs of two results from Gessel and Sagan (1996) which present new evaluations of the Tutte polynomial concerning orientations. A theorem of Massey et al (1997) gives an expression concerning the average …
-
Graph Coloring, Zero Forcing, and Related Problems
… I present new efficient methods to compute the chromatic and flow polynomials of specific families of graphs. The chromatic and flow polynomials count the number of ways to color and assign flow to the graph, and encode information relevant to various physical applications. The second part of …