Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Amazing Chromatic Polynomial
85
0
0.0
(
0
)
Authors
Bruce E Sagan
Ask ChatGPT about the research
No Arabic abstract
Let G be a combinatorial graph with vertices V and edges E. A proper coloring of G is an assignment of colors to the vertices such that no edge connects two vertices of the same color. These are the colorings considered in the famous Four Color Theorem. It turns out that the number of proper colorings of G using t colors is a polynomial in t, called the chromatic polynomial of G. This polynomial has many wonderful properties. It also has the surprising habit of appearing in contexts which, a priori, have nothing to do with graph coloring. We will survey three such instances involving acyclic orientations, hyperplane arrangements, and increasing forests. In addition, connections to symmetric functions and algebraic geometry will be mentioned.
rate research
Read More
We consider proper colorings of planar graphs embedded in the annulus, such that vertices on one rim can take Q_s colors, while all remaining vertices can take Q colors. The corresponding chromatic polynomial is related to the partition function of a boundary loop model. Using results for the latter, the phase diagram of the coloring problem (with real Q and Q_s) is inferred, in the limits of two-dimensional or quasi one-dimensional infinite graphs. We find in particular that the special role played by Beraha numbers Q=4 cos^2(pi/n) for the usual chromatic polynomial does not extend to the case Q different from Q_s. The agreement with (scarce) existing numerical results is perfect; further numerical checks are presented here.
Let $P(G,lambda)$ denote the number of proper vertex colorings of $G$ with $lambda$ colors. The chromatic polynomial $P(C_n,lambda)$ for the cycle graph $C_n$ is well-known as $$P(C_n,lambda) = (lambda-1)^n+(-1)^n(lambda-1)$$ for all positive integers $nge 1$. Also its inductive proof is widely well-known by the emph{deletion-contraction recurrence}. In this paper, we give this inductive proof again and three other proofs of this formula of the chromatic polynomial for the cycle graph $C_n$.
In this paper, we propose an algebraic approach to determine whether two non-isomorphic caterpillar trees can have the same symmetric function generalization of the chromatic polynomial. On the set of all composition on integers, we introduce: An operation, which we call composition product; and a combinatorial polynomial, which we call the composition-lattice polynomial or L-polynomial, that mimics the weighted graph polynomial of Noble and Welsh. We prove a unique irreducible factorization theorem and establish a connection between the L-polynomial of a composition and its irreducible factorization, namely that reversing irreducible factors does not change L, and conjecture that is the only way of generating such compositions. Finally, we find a sufficient condition for two caterpillars have a different symmetric function generalization of the chromatic polynomial, and use this condition to show that if our conjecture were to hold, then the symmetric function generalization of the chromatic polynomial distinguishes among a large class of caterpillars.
We determine the asymptotic behaviour of the chromatic number of exchangeable random graphs defined by step-regulated graphons. Furthermore, we show that the upper bound holds for a general graphon. We also extend these results to sparse random graphs obtained by percolations on graphons.
For graph $G$ and integers $a_1 ge cdots ge a_r ge 2$, we write $G rightarrow (a_1 ,cdots ,a_r)^v$ if and only if for every $r$-coloring of the vertex set $V(G)$ there exists a monochromatic $K_{a_i}$ in $G$ for some color $i in {1, cdots, r}$. The vertex Folkman number $F_v(a_1 ,cdots ,a_r; s)$ is defined as the smallest integer $n$ for which there exists a $K_s$-free graph $G$ of order $n$ such that $G rightarrow (a_1 ,cdots ,a_r)^v$. It is well known that if $G rightarrow (a_1 ,cdots ,a_r)^v$ then $chi(G) geq m$, where $m = 1+ sum_{i=1}^r (a_i - 1)$. In this paper we study such Folkman graphs $G$ with chromatic number $chi(G)=m$, which leads to a new concept of chromatic Folkman numbers. We prove constructively some existential results, among others that for all $r,s ge 2$ there exist $K_{s+1}$-free graphs $G$ such that $G rightarrow (s,cdots_r,s)^v$ and $G$ has the smallest possible chromatic number $r(s-1)+1$ for this $r$-color arrowing to hold. We also conjecture that, in some cases, our construction is the best possible, in particular that for every $s ge 2$ there exists a $K_{s+1}$-free graph $G$ on $F_v(s,s; s+1)$ vertices with $chi(G)=2s-1$ such that $G rightarrow (s,s)^v$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
