Search

The DP-coloring is a generalization of the list coloring, introduced by Dvořák and Postle. Let H = (L , H) be a cover of a graph G and P DP (G , H) be the number of H -colorings of G. The DP color function P DP (G , m) of G, introduced by Kaul and Mudrock, is the minimum value of P DP (G , H) where the minimum is taken over all possible m-fold covers H of G. For the family of n-vertex connected graphs, one can deduce that trees maximize the DP color function, from two results of Kaul and Mudrock. In this paper we obtain tight upper bounds for the DP color function of n-vertex 2-connected graphs. Another concern in this paper is the canonical labeling in a cover. It is well known that if an m-fold cover H of a graph G has a canonical labeling, then P DP (G , H) = P (G , m) in which P(G, m) is the chromatic polynomial of G. However the converse statement of this conclusion is not always true. We give examples that for some m and G, there exists an m-fold cover H of G such that P DP (G , H) = P (G , m) , but H has no canonical labelings. We also prove that when G is a unicyclic graph or a theta graph, for each m ≥ 3 , if P DP (G , H) = P (G , m) , then H has a canonical labeling. [ABSTRACT FROM AUTHOR]

Chromatic symmetric functions are well-studied symmetric functions in algebraic combinatorics that generalize the chromatic polynomial and are related to Hessenberg varieties and diagonal harmonics. Motivated by the Stanley–Stembridge conjecture, we show that the allowable coloring weights for indifference graphs of Dyck paths are the lattice points of a permutahedron P λ , and we give a formula for the dominant weight λ . Furthermore, we conjecture that such chromatic symmetric functions are Lorentzian, a property introduced by Brändén and Huh as a bridge between discrete convex analysis and concavity properties in combinatorics, and we prove this conjecture for abelian Dyck paths. We extend our results on the Newton polytope to incomparability graphs of (3 + 1) -free posets, and we give a number of conjectures and results stemming from our work, including results on the complexity of computing the coefficients and relations with the ζ map from diagonal harmonics. [ABSTRACT FROM AUTHOR]

We prove that for any graph G of maximum degree at most Δ, the zeros of its chromatic polynomial χ G (x) (in C) lie inside the disc of radius 5.94Δ centered at 0. This improves on the previously best known bound of approximately 6.91Δ. We also obtain improved bounds for graphs of high girth. We prove that for every g there is a constant K g such that for any graph G of maximum degree at most Δ and girth at least g , the zeros of its chromatic polynomial χ G (x) lie inside the disc of radius K g Δ centered at 0, where K g is the solution to a certain optimization problem. In particular, K g < 5 when g ≥ 5 and K g < 4 when g ≥ 25 and K g tends to approximately 3.86 as g → ∞. Key to the proof is a classical theorem of Whitney which allows us to relate the chromatic polynomial of a graph G to the generating function of so-called broken-circuit-free forests in G. We also establish a zero-free disc for the generating function of all forests in G (aka the partition function of the arboreal gas) which may be of independent interest. [ABSTRACT FROM AUTHOR]

Let C k (n) denote the family of all connected graphs of order n with chromatic number k. In this paper we show that the conjecture proposed by Tomescu which if x ≥ k ≥ 4 and G ∈ C k (n) , then P (G , x) ≤ (x) k (x - 1) n - k holds under the additional condition that G has an independent cut-set T of size at most 2 such that the number of components in G \ T is equal to the independence number of G. [ABSTRACT FROM AUTHOR]

We prove that for every path H $H$, and every integer d $d$, there is a polynomial f $f$ such that every graph G $G$ with chromatic number greater than f( t ) $f(t)$ either contains H $H$ as an induced subgraph, or contains as a subgraph the complete d $d$‐partite graph with parts of cardinality t $t$. For t = 1 $t=1$ and general d $d$ this is a classical theorem of Gyárfás, and for d = 2 $d=2$ and general t $t$ this is a theorem of Bonamy et al. [ABSTRACT FROM AUTHOR]

We show that for any non-real algebraic number q, such that | q - 1 | > 1 or ℜ (q) > 3 2 it is #P-hard to compute a multiplicative (resp. additive) approximation to the absolute value (resp. argument) of the chromatic polynomial evaluated at q on planar graphs. This implies #P-hardness for all non-real algebraic q on the family of all graphs. We, moreover, prove several hardness results for q, such that | q - 1 | ≤ 1 . Our hardness results are obtained by showing that a polynomial time algorithm for approximately computing the chromatic polynomial of a planar graph at non-real algebraic q (satisfying some properties) leads to a polynomial time algorithm for exactly computing it, which is known to be hard by a result of Vertigan. Many of our results extend in fact to the more general partition function of the random cluster model, a well-known reparametrization of the Tutte polynomial. [ABSTRACT FROM AUTHOR]

The bialgebra of hypergraphs, a generalization of W. Schmitt's Hopf algebra of graphs [ 25 ], is shown to have a cointeracting bialgebra structure, giving a double bialgebra in the sense of L. Foissy, who has recently proven [ 15 ] that there is then a unique double bialgebra morphism to the double bialgebra structure on the polynomial ring |${\mathbb Q}[x]$|⁠. We show that the associated polynomial is the hypergraph chromatic polynomial. Moreover, hypergraphs occur in quartets: There is a dual, a complement, and a dual complement hypergraph. These correspondences are involutions and give rise to three other double bialgebras, and three more chromatic polynomials. In addition to these two quartets of bialgebras we give six more, including recent bialgebras of hypergraphs introduced by M. Aguiar and F. Ardila [ 1 ] and by L. Foissy [ 17 ]. [ABSTRACT FROM AUTHOR]

The goal of this paper is to show the existence (using probabilistic tools) of configurations of lines, boxes, and points with certain interesting combinatorial properties. (i) First, we construct a family of n$$ n $$ lines in ℝ3$$ {\mathbb{R}}^3 $$ whose intersection graph is triangle‐free of chromatic number Ω(n1/15)$$ \Omega \left({n}^{1/15}\right) $$. This improves the previously best known bound Ω(loglogn)$$ \Omega \left(\mathrm{loglog}n\right) $$ by Norin, and is also the first construction of a triangle‐free intersection graph of simple geometric objects with polynomial chromatic number. (ii) Second, we construct a set of n$$ n $$ points in ℝd$$ {\mathbb{R}}^d $$, whose Delaunay graph with respect to axis‐parallel boxes has independence number at most n·(logn)−(d−1)/2+o(1)$$ n\cdotp {\left(\log n\right)}^{-\left(d-1\right)/2+o(1)} $$. This extends the planar case considered by Chen, Pach, Szegedy, and Tardos. [ABSTRACT FROM AUTHOR]

Many graph polynomials may be derived from the coefficients of the chromatic symmetric function XG ${X}_{G}$ of a graph G $G$ when expressed in different bases. For instance, the chromatic polynomial is obtained by mapping pn→x ${p}_{n}\to x$ for each n $n$ in this function, while a polynomial whose coefficients enumerate acyclic orientations is obtained by mapping en→x ${e}_{n}\to x$ for each n $n$. In this paper, we study a new polynomial we call the tree polynomial arising by mapping XPn→x ${X}_{{P}_{n}}\to x$, where XPn ${X}_{{P}_{n}}$ is the chromatic symmetric function of a path with n $n$ vertices. In particular, we show that this polynomial has a deletion‐contraction relation and has properties closely related to the chromatic polynomial while having coefficients that enumerate certain spanning trees and edge cutsets. [ABSTRACT FROM AUTHOR]

The fuzzy graph theory has many applications in solving various problems in multiple fields, including networking, communications, clustering, planning, and scheduling. In this article, we introduce the fundamental set of a picture fuzzy graph (PFG) and the (θ , ρ , σ) -level graph ( (θ , ρ , σ) -LG) of a PFG, illustrating these concepts with an example. We then discuss the properties of the (θ , ρ , σ) -LGs of a PFG. Additionally, we introduce the concept of the chromatic polynomial (CP) of a PFG, providing a demonstration with an example using (θ , ρ , σ) -LGs of a PFG and exploring various properties of CP of a PFG. Furthermore, we construct an algorithm, which is executed using Matlab. This algorithm enables us to determine the number of distinct ways to colour a PFG with a specified number of colours. The application of the work presented is to answer the question: How does the picture fuzzy model propose to rectify the inefficiency in traffic signal timing where equal time is allocated to each vehicle in a flow based on vehicle count, leading to potential delays for vehicles with different characteristics, such as motorcycles and containers? [ABSTRACT FROM AUTHOR]

The chromatic polynomial of a graph G $G$, denoted P(G,m) $P(G,m)$, is equal to the number of proper m $m$‐colorings of G $G$. The list color function of graph G $G$, denoted Pℓ(G,m) ${P}_{\ell }(G,m)$, is a list analogue of the chromatic polynomial that has been studied since the early 1990s, primarily through comparisons with the corresponding chromatic polynomial. It is known that for any graph G $G$ there is a k∈N $k\in {\mathbb{N}}$ such that Pℓ(G,m)=P(G,m) ${P}_{\ell }(G,m)=P(G,m)$ whenever m≥k $m\ge k$. The list color function threshold ofG $G$, denoted τ(G) $\tau (G)$, is the smallest k≥χ(G) $k\ge \chi (G)$ such that Pℓ(G,m)=P(G,m) ${P}_{\ell }(G,m)=P(G,m)$ whenever m≥k $m\ge k$. In 2009, Thomassen asked whether there is a universal constant α $\alpha $ such that for any graph G $G$, τ(G)≤χℓ(G)+α $\tau (G)\le {\chi }_{\ell }(G)+\alpha $, where χℓ(G) ${\chi }_{\ell }(G)$ is the list chromatic number of G $G$. We show that the answer to this question is no by proving that there exists a positive constant C $C$ such that τ(K2,l)−χℓ(K2,l)≥Cl $\tau ({K}_{2,l})-{\chi }_{\ell }({K}_{2,l})\ge C\sqrt{l}$ for l≥16 $l\ge 16$. [ABSTRACT FROM AUTHOR]

This paper studies the chromatic polynomial of some special graphs like path graph, ladder graph and grid graph using the concept of digonalization of transfer matrix to solve simultaneous recurrence relation. The aim of this paper is to solve an open problem on the chromatic polynomial of grid graph (Problem 8.1 of Selected Topics in Graph Theory, Volume 3 which is edited by Lowell W. Beineke and Robin J. Wilson) and give general formula of the chromatic polynomial in λ of grid graph P 3 □ P n , where n ∈ N without any condition on n where λ denotes number of available colors. [ABSTRACT FROM AUTHOR]

The planar graph product structure theorem of Dujmovi\'c et al. [J. ACM, 67 (2020), 22] states that every planar graph is a subgraph of the strong product of a graph with bounded treewidth and a path. This result has been the key tool to resolve important open problems regarding queue layouts, nonrepetitive colorings, centered colorings, and adjacency labeling schemes. In this paper, we extend this line of research by utilizing shallow minors to prove analogous product structure theorems for several beyond-planar graph classes. The key observation that drives our work is that many beyond-planar graphs can be described as a shallow minor of the strong product of a planar graph with a small complete graph. In particular, we show that powers of bounded degree planar graphs, k-planar, (k, p)-cluster planar, fan-planar, and k-fan-bundle planar graphs have such a shallow-minor structure. Using a combination of old and new results, we deduce that these classes have bounded queue-number, bounded nonrepetitive chromatic number, polynomial p-centered chromatic numbers, linear strong coloring numbers, and cubic weak coloring numbers. In addition, we show that k-gap planar graphs have at least exponential local treewidth and, as a consequence, cannot be described as a subgraph of the strong product of a graph with bounded treewidth and a path. [ABSTRACT FROM AUTHOR]

A graph G is chromatically unique if its chromatic polynomial completely determines the graph. An n-spoked wheel, Wn, is shown to be chromatically unique when n ≥ 4 is even [S.-J. Xu and N.-Z. Li, The chromaticity of wheels, Discrete Math. 51 (1984) 207-212]. When n is odd, this problem is still open for n ≥ 15 since 1984, although it was shown by different researchers that the answer is no for n = 5, 7, yes for n = 3, 9, 11, 13, and unknown for other odd n. We use the beta invariant of matroids to prove that if M is a 3-connected matroid such that |E(M)| = |E(Wn)| and β(M) = β(M(Wn)), where β(M) is the beta invariant of M, then M ∼= M(Wn). As a consequence, if G is a 3-connected graph such that the chromatic (or flow) polynomial of G equals to the chromatic (or flow) polynomial of a wheel, then G is isomorphic to the wheel. The examples for n = 3, 5 show that the 3-connectedness condition may not be dropped. We also give a splitting formula for computing the beta invariants of general parallel connection of two matroids as well as the 3-sum of two binary matroids. This generalizes the corresponding result of [T.H. Brylawski, A combinatorial model for series-parallel networks, Trans. Amer. Math. Soc. 154 (1971) 1-22]. [ABSTRACT FROM AUTHOR]

The Gyárfás-Sumner conjecture says that for every forest H and every integer k , if G is H -free and does not contain a clique on k vertices then it has bounded chromatic number. (A graph is H-free if it does not contain an induced copy of H.) Kierstead and Penrice proved it for trees of radius at most two, but otherwise the conjecture is known only for a few simple types of forest. More is known if we exclude a complete bipartite subgraph instead of a clique: Rödl showed that, for every forest H , if G is H -free and does not contain K t , t as a subgraph then it has bounded chromatic number. In an earlier paper with Sophie Spirkl, we strengthened Rödl's result, showing that for every forest H , the bound on chromatic number can be taken to be polynomial in t. In this paper, we prove a related strengthening of the Kierstead-Penrice theorem, showing that for every tree H of radius two and integer d ≥ 2 , if G is H -free and does not contain as a subgraph the complete d -partite graph with parts of cardinality t , then its chromatic number is at most polynomial in t. [ABSTRACT FROM AUTHOR]

Objectives: The aim of this article is to enhance the understanding of the computation of chromatic polynomials and chromatic index polynomials, and to facilitate their practical use in various fields by demonstrating and supporting the proposed algorithms. Results: The theorems for computing the chromatic polynomial and chromatic index polynomial are thoroughly demonstrated and validated in this article. Additionally, the algorithms used in these computations are introduced and explained.

Graph Theory is a discipline of mathematics with numerous outstanding issues and applications in a variety of sectors of mathematics and science. The chromatic polynomial is a type of polynomial that has useful and attractive qualities. Ehrhart's polynomials and chromatic analysis are two essential techniques for graph analysis. They both provide insight into the graph's structure but in different ways. The relationship between chromatic and Ehrhart polynomials is an area of active research that has implications for graph theory, combinatorial, and other fields. By understanding the relationship between these two polynomials, one can better understand the structure of graphs and how they interact with each other. This can help us to solve complex problems in our lives more efficiently and effectively. This work gives the relationship between these two essential polynomials and the proof of theorems and an application related to these works was discussed, which is the model Physical Cell ID (PCID).

In 1997, Sierpinski graphs, S (n , k) , were obtained by Klavzar and Milutinovic. The graph S (1 , k) represents the complete graph K k and S (n , 3) is known as the graph of the Tower of Hanoi. Through generalizing the notion of a Sierpinski graph, a graph named a generalized Sierpinski graph, denoted by S i e (Λ , t) , already exists in the literature. For every graph, numerous polynomials are being studied, such as chromatic polynomials, matching polynomials, independence polynomials, and the M-polynomial. For every polynomial there is an underlying geometrical object which extracts everything that is hidden in a polynomial of a common framework. Now, we describe the steps by which we complete our task. In the first step, we generate an M-polynomial for a generalized Sierpinski graph S i e (Λ , t) . In the second step, we extract some degree-based indices of a generalized Sierpinski graph S i e (Λ , t) using the M-polynomial generated in step 1. In step 3, we generate the entropy of a generalized Sierpinski graph S i e (Λ , t) by using the Randić index. [ABSTRACT FROM AUTHOR]

Boesch, Li, and Suffel were the first to identify the existence of uniformly optimally reliable graphs (UOR graphs), graphs which maximize all-terminal reliability over all graphs with n vertices and m edges. The all-terminal reliability of a graph, and more generally a graph's all-terminal reliability polynomial R (G ; p) , may both be obtained via the Tutte polynomial T (G ; x , y) of the graph G. Here we show that the UOR graphs found earlier are in fact maximum graphs for the Tutte polynomial itself, in the sense that they are maximum not just for all-terminal reliability but for a vast array of other parameters and polynomials that may be obtained from T (G ; x , y) as well. These parameters include, but are not limited to, enumerations of a wide variety of well-known orientations, partial orientations, and fourientations of G ; the magnitudes of the coefficients of the chromatic and flow polynomials of G ; and a wide variety of generating functions, such as generating functions enumerating spanning forests and spanning connected subgraphs of G. The maximality of all of these parameters is done in a unified way through the use of (n , m) Tutte polynomial posets. [ABSTRACT FROM AUTHOR]

A hole in a graph G $G$ is an induced cycle of length at least four, and a k $k$‐multihole in G $G$ is the union of k $k$ pairwise disjoint and nonneighbouring holes. It is well known that if G $G$ does not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any integer k≥1 $k\ge 1$, if G $G$ does not contain a k $k$‐multihole, then its chromatic number is at most a polynomial function of its clique number. We show that the same result holds if we ask for all the holes to be odd or of length four; and if we ask for the holes to be longer than any fixed constant or of length four. This is part of a broader study of graph classes that are polynomially χ $\chi $‐bounded. [ABSTRACT FROM AUTHOR]

We consider a problem proposed by Linial and Wilf to determine the structure of graphs that allows the maximum number of q-colorings among graphs with n vertices and m edges. Let Tr(n) denote the Tur\'an graph--the complete r-partite graph on n vertices with partition sizes as equal as possible. We prove that for all odd integers q\geq 5 and sufficiently large n, the Tur\'an graph T2(n) has at least as many q-colorings as any other graph G with the same number of vertices and edges as T2(n), with equality holding if and only if G=T2(n). Our proof builds on methods by Norine and by Loh, Pikhurko, and Sudakov, which reduces the problem to a quadratic program. [ABSTRACT FROM AUTHOR]

A graph G is H-free if it has no induced subgraph isomorphic to H. We prove that a P 5 -free graph with clique number ω ≥ 3 has chromatic number at most ω log 2 (ω) . The best previous result was an exponential upper bound (5 / 27) 3 ω , due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for P 5 , which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for P 5 -free graphs, and our result is an attempt to approach that. [ABSTRACT FROM AUTHOR]

For any connected graph G $G$, let P(G,m) $P(G,m)$ and PDP(G,m) ${P}_{DP}(G,m)$ denote the chromatic polynomial and Dvořák and Postle (DP) color function of G $G$, respectively. It is known that PDP(G,m)≤P(G,m) ${P}_{DP}(G,m)\le P(G,m)$ holds for every positive integer m $m$. Let DP≈ $D{P}_{\approx }$ (resp., DP< $D{P}_{\lt }$) be the set of graphs G $G$ for which there exists an integer M $M$ such that PDP(G,m)=P(G,m) ${P}_{DP}(G,m)=P(G,m)$ (resp., PDP(G,m)

This article is built upon three main ideas. First, for a class of monomial ideals, it is proved that the multiplicity of an ideal equals the number of realizations of its codimension (an intuitive concept that we define later). Next, for an arbitrary graph G, we construct a monomial ideal M G and show that the chromatic number of G is equal to the codimension of M G . Finally, for a class of graphs, we give a formula that computes the chromatic polynomial of G, evaluated at the chromatic number of G, in terms of the codimension and multiplicity of M G . In particular, the formula applies to all graphs satisfying the Erds–Faber–Lovász conjecture. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a simple graph with n vertices and m edges, P (G , k) be the chromatic polynomial of G , and P (G , L) be the number of L -colorings of G for any k -assignment L. In this article, we show that when k ≥ m − 1 ≥ 3 , P (G , L) − P (G , k) is bounded below by ((k − m + 1) k n − 3 + (k − m + 3) c 3 k n − 5) ∑ u v ∈ E | L (u) ∖ L (v) | , where c ≥ (m − 1) (m − 3) 8 , and in particular, if G is K 3 -free, then c ≥ ( m − 2 2 ) + 2 m − 3. Consequently, P (G , L) ≥ P (G , k) whenever k ≥ m − 1. [ABSTRACT FROM AUTHOR]

We introduce the Burnside chromatic polynomial of a graph that is invariant under a group action. This is a generalization of the Q-chromatic function Zaslavsky introduced for gain graphs. Given a group 𝕲 acting on a graph G and a 𝕲-set X, a proper X-coloring is a function with no monochromatic edge orbit. The set of proper colorings is a 𝕲-set which induces a polynomial function from the Burnside ring of 𝕲 to itself. In this paper, we study many properties of the Burnside chromatic polynomial, answering some questions of Zaslavsky.

Let F t (n) denote the family of all connected graphs of order n with clique number t. In this paper, we present a new upper bound for the chromatic polynomial of a graph G in F t (n) in terms of the clique number of G. Moreover, we also show that the conjecture proposed by Tomescu, which says that if x ≥ k ≥ 4 and G is a connected graph on n vertices with chromatic number k, then P (G , x) ≤ (x) k (x - 1) n - k holds under certain conditions, where (x) k = x (x - 1) ⋯ (x - k + 1) , such as the clique number ω (G) = k ≥ 4 , ω (G) = k - 1 (k ≥ 7) with two (k - 1) -cliques having at most k - 3 vertices in common, or maximum degree ▵ (G) = n - 2 . [ABSTRACT FROM AUTHOR]

DP-coloring (also called correspondence coloring) is a generalization of list coloring that has been widely studied in recent years after its introduction by Dvořák and Postle in 2015. The chromatic polynomial of a graph is an extensively studied notion in combinatorics since its introduction by Birkhoff in 1912; denoted P(G, m), it equals the number of proper m-colorings of graph G. Counting function analogues of the chromatic polynomial have been introduced and studied for list colorings: P ℓ , the list color function (1990); DP colorings: P DP , the DP color function (2019), and P DP ∗ , the dual DP color function (2021). For any graph G and m ∈ N , P DP (G , m) ≤ P ℓ (G , m) ≤ P (G , m) ≤ P DP ∗ (G , m) . A function f is chromatic-adherent if for every graph G, f (G , a) = P (G , a) for some a ≥ χ (G) implies that f (G , m) = P (G , m) for all m ≥ a . It is not known if the list color function and the DP color function are chromatic-adherent. We show that the DP color function is not chromatic-adherent by studying the DP color function of Generalized Theta graphs. The tools we develop along with the Rearrangement Inequality give a new method for determining the DP color function of all Theta graphs and the dual DP color function of all Generalized Theta graphs. [ABSTRACT FROM AUTHOR]

DP‐coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvořák and Postle in 2015. Motivated by results related to list coloring Cartesian products of graphs, we initiate the study of the DP‐chromatic number, χDP ${\chi }_{DP}$, of the same. We show that χDP(G□H)≤min{χDP(G)+col(H),χDP(H)+col(G)}−1 ${\chi }_{DP}(G\,\square \,H)\le \,\text{min}\,\{{\chi }_{DP}(G)\,+\text{col}(H),{\chi }_{DP}(H)+\text{col}\,(G)\}-1$, where col(H) $\,\text{col}\,(H)$ is the coloring number of the graph H $H$. We focus on building tools for lower bound arguments for χDP(G□H) ${\chi }_{DP}(G\,\,\square \,\,H)$ and use them to show the sharpness of the bound above and its various forms. Our results illustrate that the DP‐color function of G $G$, the DP analogue of the chromatic polynomial, is essential in the study of the DP‐chromatic number of the Cartesian product of graphs, including the following question that extends the sharpness problem above and the classical result on gap between list‐chromatic number and chromatic number: given any graph G $G$ and k∈N $k\in {\mathbb{N}}$, what is the smallest t $t$ for which χDP(G□Kk,t)=χDP(G)+k ${\chi }_{DP}(G\,\square \,{K}_{k,t})={\chi }_{DP}(G)+k$? [ABSTRACT FROM AUTHOR]

A topological index of a graph G is a real number which is preserved under isomorphism. Extensive studies on certain polynomials related to these topological indices have also been done recently. In a similar way, chromatic versions of certain topological indices and the related polynomials have also been discussed in the recent literature. In this paper, the chromatic versions of the Schultz polynomial and modified chromatic Schultz polynomial are introduced and determined this polynomial for certain fundamental graph classes. [ABSTRACT FROM AUTHOR]

Let H be a tree. It was proved by Rödl that graphs that do not contain H as an induced subgraph, and do not contain the complete bipartite graph Kt,t as a subgraph, have bounded chromatic number. Kierstead and Penrice strengthened this, showing that such graphs have bounded degeneracy. Here we give a further strengthening, proving that for every tree H , the degeneracy is at most polynomial in t . This answers a question of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak. [ABSTRACT FROM AUTHOR]

Probably the best strategy to give a computer-free proof of the 4-color theorem is to show that the chromatic polynomial of any planar graph evaluated at 4 is nonzero. After making assumptions like no danglers and adding edges if necessary, a connected graph is a "web" of "interlocking wheels". If G is a web of k interlocking wheels obtained from a planar graph, it is conjectured that its chromatic polynomial P (G , t) = P 1 (t) + ⋯ + P k (t) with all P j (4) > 0 . In this paper, we prove the conjecture in the base case of the interlocking wheels W m ∧ 2 W n for k = 2 . As a byproduct, in the last section we apply our result to exponentially simplify the computations to find some interesting facts about a real life graph. [ABSTRACT FROM AUTHOR]

The chromatic polynomial is a graph polynomial that is explored in algebraic graph theory. It was invented by George David Birkhoff to examine the four-color problem and it counts the number of graph colorings as a function of the number of colors. In this paper, we provide Chromatic polynomials for rooted graphs, trees, and rooted trees, as well as particular methods for their computation, the relationship between chromatic polynomial and Tutte polynomial for rooted graphs. We conclude by giving real-life examples and applications of polynomials. [ABSTRACT FROM AUTHOR]

Colour science has had a very long history, dotted over the millennia with many contributions from the most diverse fields of human knowledge. At the beginning of the 20th century, Albert Henry Munsell, an artist formally trained in academia, and Friedrich Wilhelm Ostwald, Nobel prize for chemistry in 1909 and amateur painter, each envisioned and developed a colour system with a related colour atlas. Both authors recognized the importance of the visual relationship between colours, which they conceived as sensations stemming from, but not merely confined to, pigments and light. We hereby describe the salient features of these colour spaces, their strengths and weaknesses, the authors' analogy of intents and divergence in execution. The contribution of this paper is a discussion on how these are employed both in Italian educational facilities, and salon practice, as well as a suggestion about their use within the industry of human hair cosmetics. [ABSTRACT FROM AUTHOR]

The Tutte polynomial, a considerable generalization of the chromatic polynomial, associated with a graph is a classical bivariate polynomial, which gives various interesting information about the graph structure. In this paper, we first present a formula for the Tutte polynomial of a class of special compound graphs. Then as applications, we obtain the Tutte polynomials of some complex network models in the context of statistical physics and the Tutte polynomials of some chemical polycyclic graphs. Moreover, explicit expressions of the number of spanning trees for these considered graphs are determined, respectively. [ABSTRACT FROM AUTHOR]

A (proper) k -coloring of a graph G = (V , E) is a function c : V (G) → { 1 , ... , k } such that c (u) ≠ c (v) , for every u v ∈ E (G). Given a graph G and a spanning subgraph H of G , a (circular) q -backbone k -coloring of (G , H) is a k -coloring c of G such that q ≤ | c (u) − c (v) | (q ≤ | c (u) − c (v) | ≤ k − q), for every edge u v ∈ E (H). The (circular) q -backbone chromatic number of (G , H) , denoted by BBC q (G , H) ( CBC q (G , H)), is the minimum integer k for which there exists a (circular) q -backbone k -coloring of (G , H). In this work, we (partially) answer three questions posed by Havet et al. (2014), namely, we prove that if G is a planar graph, H is a spanning subgraph of G and q is a positive integer, then: CBC q (G , H) ≤ 2 q + 2 when q ≥ 3 and H is a galaxy; CBC q (G , H) ≤ 2 q when q ≥ 4 and H is a matching; and CBC 3 (G , H) ≤ 7 when H is a matching and G has no triangles sharing an edge. In addition, we present a polynomial-time algorithm to determine both parameters for any pair (G , H) , whenever G has bounded treewidth. Finally, we show how to fix a mistake in a proof that BBC 2 (G , M) ≤ Δ (G) + 1 , for any matching M of an arbitrary graph G (Miškuf et al., 2010). [ABSTRACT FROM AUTHOR]

Matiyasevich formula which expresses the chromatic polynomial of an arbitrary graph through a linear combination of flow polynomials of subgraphs of the original graph is generalized by using the Feynman amplitudes technique. The article presents a formula expressing a flow polynomial through a linear combination of chromatic polynomials of constricted graphs. This proof is obtained by using the Feynman amplitudes technique. A simple proof of Matiyasevich formula and its consequences are derived by using the same technique. [ABSTRACT FROM AUTHOR]

Objective: In the field of graph theory, maple is a technical computation form that is used for solving problems. In this article, we apply maple to find the strong fuzzy chromatic polynomial of fuzzy graphs and related. Moreover, we apply maple to obtain strong fuzzy chromatic numbers of fuzzy graphs using their strong fuzzy chromatic polynomials. Results: The strong fuzzy chromatic polynomials for fuzzy graphs, strong fuzzy graphs and complete fuzzy graphs are determined using maple. Furthermore, the strong fuzzy chromatic numbers for the fuzzy graphs are obtained. [ABSTRACT FROM AUTHOR]

We show that Khovanov link homology is trivial in a range of gradings and utilize relations between Khovanov and chromatic graph homology to determine extreme Khovanov groups and corresponding coefficients of the Jones polynomial. The extent to which chromatic homology and the chromatic polynomial can be used to compute integral Khovanov homology of a link depends on the maximal girth of its all-positive graphs. In this paper, we define the girth of a link, discuss relations to other knot invariants, and describe possible values for girth. Analyzing girth leads to a description of possible all-A state graphs of any given link; e.g., if a link has a diagram such that the girth of the corresponding all-A graph is equal to ℓ > 2 , then the girth of the link is equal to ℓ. [ABSTRACT FROM AUTHOR]

The Tutte polynomial is an isomorphism invariant of graphs that generalizes the chromatic and the flow polynomials. This two-variable polynomial with integral coefficients is known to carry important information about the properties of the graph. It has been used to prove long-standing conjectures in knot theory. Furthermore, it is related to the Potts and Ising models in statistical physics. The purpose of this paper is to study the interaction between the Tutte polynomial and graph symmetries. More precisely, we prove that if the automorphism group of the graph G contains an element of prime order p, then the coefficients of the Tutte polynomial of G satisfy certain necessary conditions. [ABSTRACT FROM AUTHOR]

The Gyárfás–Sumner conjecture says that for every forest H $H$, there is a function fH ${f}_{H}$ such that if G $G$ is H $H$‐free then χ(G)≤fH(ω(G)) $\chi (G)\le {f}_{H}(\omega (G))$ (where χ,ω $\chi ,\omega $ are the chromatic number and the clique number of G $G$). Louis Esperet conjectured that, whenever such a statement holds, fH ${f}_{H}$ can be chosen to be a polynomial. The Gyárfás–Sumner conjecture is only known to be true for a modest set of forests H $H$, and Esperet's conjecture is known to be true for almost no forests. For instance, it is not known when H $H$ is a five‐vertex path. Here we prove Esperet's conjecture when each component of H $H$ is a star. [ABSTRACT FROM AUTHOR]

A "double star" is a tree with two internal vertices. It is known that the Gyárfás–Sumner conjecture holds for double stars, that is, for every double star H $H$, there is a function fH ${f}_{H}$ such that if G $G$ does not contain H $H$ as an induced subgraph then χ(G)≤fH(ω(G)) $\chi (G)\le {f}_{H}(\omega (G))$ (where χ,ω $\chi ,\omega $ are the chromatic number and the clique number of G $G$). Here we prove that fH ${f}_{H}$ can be chosen to be a polynomial. [ABSTRACT FROM AUTHOR]

Stanley introduced the concept of chromatic symmetric functions of graphs which extends and refines the notion of chromatic polynomials of graphs, and asked whether trees are determined up to isomorphism by their chromatic symmetric functions. Using the technique of differentiation with respect to power-sum symmetric functions, we give a positive answer to Stanley's question for the class of trees with exactly two vertices of degree at least 3. In addition, we prove that for any tree T , the generalized degree sequence for subtrees of T is determined by the chromatic symmetric function of T , providing evidence to a conjecture of Crew. [ABSTRACT FROM AUTHOR]