Search

For a non-decreasing sequence of positive integers S = (s 1 , s 2 , ...) , the S -packing chromatic number χ S (G) of G is the smallest integer k such that the vertex set of G can be partitioned into sets X i , i ∈ k ] , where vertices in X i are pairwise at distance greater than s i. In this paper we introduce S -packing chromatic vertex-critical graphs, χ S -critical for short, as the graphs in which χ S (G − u) < χ S (G) for every u ∈ V (G). This extends the earlier concept of the packing chromatic vertex-critical graphs. We show that if G is χ S -critical, then the set { χ S (G) − χ S (G − u) : u ∈ V (G) } can be almost arbitrary. If G is χ S -critical and χ S (G) = k (k ∈ N), then G is called k - χ S -critical. We characterize 3- χ S -critical graphs and partially characterize 4- χ S -critical graphs when s 1 > 1. We also deal with k - χ S -criticality of trees and caterpillars. [ABSTRACT FROM AUTHOR]

Given a graph G and a nondecreasing sequence S = (s 1 , ... , s k) of positive integers, the mapping c : V (G) ⟶ { 1 , ... , k } is called an S-packing coloring of G if for any two distinct vertices x and y in c - 1 (i) , the distance between x and y is greater than s i . The smallest integer k such that there exists a (1 , 2 , ... , k) -packing coloring of a graph G is called the packing chromatic number of G, denoted χ ρ (G) . The question of boundedness of the packing chromatic number in the class of subcubic (planar) graphs was investigated in several earlier papers; recently it was established that the invariant is unbounded in the class of all subcubic graphs. In this paper, we prove that the packing chromatic number of any 2-connected bipartite subcubic outerplanar graph is bounded by 7. Furthermore, we prove that every subcubic triangle-free outerplanar graph has a (1, 2, 2, 2)-packing coloring, and that there exists a subcubic outerplanar graph with a triangle that does not admit a (1, 2, 2, 2)-packing coloring. In addition, there exists a subcubic triangle-free outerplanar graph that does not admit a (1, 2, 2, 3)-packing coloring. A similar dichotomy is shown for bipartite outerplanar graphs: every such graph admits an S-packing coloring for S = (1 , 3 , ... , 3) , where 3 appears Δ times (Δ being the maximum degree of vertices), and this property does not hold if one of the integers 3 is replaced by 4 in the sequence S. [ABSTRACT FROM AUTHOR]

For a positive integer k, a radio k-coloring of a simple connected graph G = (V(G), E(G)) is a mapping f : V (G) → { 0 , 1 , 2 , ... } such that | f (u) - f (v) | ≥ k + 1 - d (u , v) for each pair of distinct vertices u and v of G, where d(u, v) is the distance between u and v in G. The span of a radio k-coloring f, rck(f), is the maximum integer assigned by it to some vertex of G. The radio k-chromatic number, rck(G) of G is min{rck(f)}, where the minimum is taken over all radio k-colorings f of G. If k is the diameter of G, then rck(G) is known as the radio number of G. In this paper, we propose an improved upper bound of radio k-chromatic number for a given graph against the other which is due to Saha and Panigrahi (in: Arumugan, Smyth (eds) Combinatorial algorithms (IWOCA 2012). Lecure notes in computer science, vol 7643, Springer, Berlin, 2012). The computational study shows that the proposed algorithm overcomes the previous algorithm. We introduce a polynomial algorithm [differs from the other that is due to Liu and Zhu (SIAM J Discrete Math 19(3):610–621, 2005)] which determines the radio number of the path graph Pn. Finally, we propose a new integer linear programming model for the radio k-coloring problem. The computational study between the proposed algorithm and LINGO solver shows that the proposed algorithm overcomes LINGO solver. [ABSTRACT FROM AUTHOR]

Let G be a connected undirected graph without loops and multiple edges. By | G | , η (G) , and m (G) we, respectively, denote the order, the nullity, and the matching number of G. Let c (G) = | E (G) | − | G | + 1 , and let θ (G) be a nonnegative integer defined as: To make G to be a bipartite connected graph at least θ (G) edges of G must be deleted from G. In this note, applying an operation called bipartite double, we prove that | G | − 2 m (G) − θ (G) ≤ η (G) for an arbitrary connected graph G. This result improves a main result in Wang and Wong [Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank. Disc Appl Math. 2014;166:276–281] saying that | G | − 2 m (G) − c (G) ≤ η (G) for a connected graph G. [ABSTRACT FROM AUTHOR]

We investigate group‐theoretic "signatures" of odd cycles of a graph, and their connections to topological obstructions to 3‐colourability. In the case of signatures derived from free groups, we prove that the existence of an odd cycle with trivial signature is equivalent to having the coindex of the hom‐complex at least 2 (which implies that the chromatic number is at least 4). In the case of signatures derived from elementary abelian 2‐groups we prove that the existence of an odd cycle with trivial signature is a sufficient condition for having the index of the hom‐complex at least 2 (which again implies that the chromatic number is at least 4). [ABSTRACT FROM AUTHOR]

A simple graph G is called Δ -critical if χ ′ (G) = Δ (G) + 1 and χ ′ (H) ≤ Δ (G) for every proper subgraph H of G, where Δ (G) and χ ′ (G) are the maximum degree and the chromatic index of G, respectively. Vizing in 1965 conjectured that any Δ -critical graph contains a 2-factor, which is commonly referred to as Vizing's 2-factor conjecture; In 1968, he proposed a weaker conjecture that the independence number of any Δ -critical graph with order n is at most n/2, which is commonly referred to as Vizing's independence number conjecture. Based on a construction of Δ -critical graphs which is called Meredith extension first given by Meredith, we show that if α (G ′) ≤ (1 2 + f (Δ)) | V (G ′) | for every Δ -critical graph G ′ with δ (G ′) = Δ - 1 , then α (G) < (1 2 + f (Δ) (2 Δ - 5)) | V (G) | for every Δ -critical graph G with maximum degree Δ , where f is a nonnegative function of Δ. We also prove that any Δ -critical graph contains a 2-factor if and only if its Meredith extension contains a 2-factor. [ABSTRACT FROM AUTHOR]

We study two parameters obtained from the Euler characteristic by replacing the number of faces with that of induced and induced non-separating cycles. By establishing monotonicity of such parameters under certain homomorphism and edge contraction, we obtain new upper bounds on the chromatic number in terms of the number of induced cycles and the Hadwiger number in terms of the number of induced non-separating cycles. As an application, we show that every 3-connected graph with average degree at least 2k for some k ≥ 2 have at least (k - 1) | V | + C k 3 log 3 / 2 k induced non-separating cycles for some explicit constant C > 0 . This improves the previous best known lower bound (k - 1) | V | + 1 , which follows from Tutte's cycle space theorem. We also give a short proof of this theorem of Tutte. [ABSTRACT FROM AUTHOR]

It is proved that every connected graph G on n vertices with χ (G) ≥ 4 has at most k (k − 1) n − 3 (k − 2) (k − 3) k -colourings for every k ≥ 4. Equality holds for some (and then for every) k if and only if the graph is formed from K 4 by repeatedly adding leaves. This confirms (a strengthening of) the 4-chromatic case of a long-standing conjecture of Tomescu [29]. Proof methods may be of independent interest. In particular, one of our auxiliary results about list-chromatic polynomials solves a generalized version of a recent conjecture of Brown, Erey, and Li. [ABSTRACT FROM AUTHOR]

We investigate 4-chromatic Schrijver graphs from various points of view and color-critical edges in Schrijver graphs in general. In particular, we present the following results. We give an elementary proof for the non-3-colorability of 4-chromatic Schrijver graphs thus providing such a proof also for 4-chromatic Kneser graphs. We show that only certain types of edges of Schrijver graphs can be color-critical and prove that many of those are indeed color-critical, though in general not all of them are. In the 4-chromatic case these results give a complete characterization of the color-critical edges. We show that a spanning subgraph of 4-chromatic Schrijver graphs quadrangulates the Klein bottle, while another spanning subgraph quadrangulates the projective plane. The latter is a special case of a result by Kaiser and Stehlík. We show that (apart from two cases of small parameters) the subgraphs we present that quadrangulate the Klein bottle are edge-color-critical. The analogous result for the subgraphs quadrangulating the projective plane is an immediate consequence of earlier results by Gimbel and Thomassen and was already noted by Kaiser and Stehlík. Our proof of non-3-colorability of 4-chromatic Schrijver graphs is based on a complete description of their structure that we present as well. This was already also given (in somewhat different terms) by Braun and even earlier in an unpublished manuscript by Li. [ABSTRACT FROM AUTHOR]

In this paper, we first study a new extremal problem recently posed by Conlon and Tyomkyn [Repeated Patterns in Proper Colourings, preprint, https://arxiv.org/abs/2002.00921 (2020)]. Given a graph H and an integer k ≥ 2, let fk(n, H) be the smallest number of colors c such that there exists a proper edge coloring of the complete graph Kn with c colors containing no k vertex-disjoint color-isomorphic copies of H. Using algebraic properties of polynomials over finite fields, we give an explicit proper edge coloring of Kn and show that fk(n, C4) = θ(n) when k ≥ 3 and n→∞. The methods we used in the edge coloring may be of some independent interest. We also consider a related generalized Ramsey problem. For given graphs G and H, let r(G, H, q) be the minimum number of edge colors (not necessarily proper) of G, such that the edges of every copy of H ≤ G together receive at least q distinct colors. Establishing the relation to the Tur\'an number of specified bipartite graphs, we obtain some general lower bounds for r(Kn,n, Ks,t, q) with a broad range of q [ABSTRACT FROM AUTHOR]

Fibonacci cubes are defined as subgraphs of hypercubes, where the vertices are those without two consecutive 1's in their binary string representation. k -Fibonacci cubes are in turn special subgraphs of Fibonacci cubes obtained by eliminating certain edges. This elimination is carried out at the step analogous to where the fundamental recursion is used to construct Fibonacci cubes themselves from the two previous cubes by link edges. In this work, we calculate the vertex chromatic polynomial of k -Fibonacci cubes for k = 1, 2. We also determine the domination number and the total domination number of k -Fibonacci cubes for n, k ≤ 12 by using an integer programming formulation. [ABSTRACT FROM AUTHOR]

We report exact results concerning the zeros of the partition function of the Potts model in the complex q-plane, as a function of a temperature-like Boltzmann variable v, for the m-th iterate graphs Dm of the diamond hierarchical lattice, including the limit m → ∞. In this limit, we denote the continuous accumulation locus of zeros in the q-planes at fixed v = v0 as B q ( v 0 ). We apply theorems from complex dynamics to establish the properties of B q ( v 0 ). For v = −1 (the zero-temperature Potts antiferromagnet or, equivalently, chromatic polynomial), we prove that B q (− 1) crosses the real q-axis at (i) a minimal point q = 0, (ii) a maximal point q = 3, (iii) q = 32/27, (iv) a cubic root that we give, with the value q = q1 = 1.638 896 9..., and (v) an infinite number of points smaller than q1, converging to 32/27 from above. Similar results hold for B q ( v 0 ) for any −1 < v < 0 (Potts antiferromagnet at nonzero temperature). The locus B q ( v 0 ) crosses the real q-axis at only two points for any v > 0 (Potts ferromagnet). We also provide the computer-generated plots of B q ( v 0 ) at various values of v0 in both the antiferromagnetic and ferromagnetic regimes and compare them to the numerically computed zeros of Z(D4, q, v0). [ABSTRACT FROM AUTHOR]

The complex roots of the chromatic polynomial P G (x) of a graph G have been well studied, but the p-adic roots have received no attention as yet. We consider these roots, specifically the roots in the ring Z p of p-adic integers. We first describe how the existence of p-adic roots is related to the p-divisibility of the number of colourings of a graph—colourings by at most k colours and also ones by exactly k colours. Then we turn to the question of the circumstances under which P G (x) splits completely over Z p , giving some generalities before considering in detail an infinite family of graphs whose chromatic polynomials have been discovered, by Morgan (LMS J Comput Math 15, 281–307, 2012), to each have a cubic abelian splitting field. [ABSTRACT FROM AUTHOR]

Motivated by Dohmen–Pönitz–Tittmann's bivariate chromatic polynomial χ G (x , y) , which counts all x-colorings of a graph G such that adjacent vertices get different colors if they are ≤ y , we introduce a bivarate version of Stanley's order polynomial, which counts order preserving maps from a given poset to a chain. Our results include decomposition formulas in terms of linear extensions, a combinatorial reciprocity theorem, and connections to bivariate chromatic polynomials. [ABSTRACT FROM AUTHOR]

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by atmost one. The notion of equitable coloring was introduced by Meyer in 1973. A proper h-colorable graph K is said to be equitably h-colorable if the vertex sets of K can be partioned into h independent color classes V1, V2, ..., Vh such that the condition ||Vi| - |Vj|| ≤ 1 holds for all different pairs of i and j and the least integer h is known as equitable chromatic number of K. In this paper, we find the equitable coloring of book graph, middle, line and central graphs of book graph. [ABSTRACT FROM AUTHOR]

Let C(n,k) denote the family of connected graphs having order n and chromatic number k. In [I. Tomescu, J. Graph Theory, 43(2003), 210-222] a partial order relation between the graphs in C(n,k) was defined by using the coefficients of the chromatic polynomial in factorial form and the first [n/2] levels of the diagram of the poset C(n, 3) were described. Later in [I. Tomescu, S. Javed, J. Graphs and Combinatorics 31(2015), 1043-1052] the next ([n/2] + 1)-st level was analysed. This paper is focused on the ([n/2] + 2)-nd level and it is shown that this level contains (n² -2n+4)/4 bicyclic graphs for even n and (n+1)²/4 bicyclic graphs for odd n. [ABSTRACT FROM AUTHOR]

Chromatic polynomials of graphs have been studied extensively for around one century. The concept of chromatic polynomial of a hypergraph is a natural extension of chromatic polynomial of a graph. It also has been studied for more than 30 years. This short article will focus on introducing some important open problems on chromatic polynomials of hypergraphs. [ABSTRACT FROM AUTHOR]

Kingdomino TM is a board game designed by Bruno Cathala and edited by Blue Orange since 2016. The goal is to place 2 × 1 dominoes on a grid layout, and get a better score than other players. Each 1 × 1 domino cell has a color that must match at least one adjacent cell, and an integer number of crowns (possibly none) used to compute the score. We prove that even with full knowledge of the future of the game, it is NP -complete to decide whether a given score is achievable at Kingdomino TM. [ABSTRACT FROM AUTHOR]

Let χ(t) = a0tn – a1tn−1 + ⋯ + (−1)rartn−r be the chromatic polynomial of a graph, the characteristic polynomial of a matroid, or the characteristic polynomial of an arrangement of hyperplanes. For any integer k = 0, 1, ..., r and real number x ⩾ k − r − 1, we obtain a linear bound of the coefficient sequence, that is (r+x k) ≤ ∑i=0kai(x k−i) ≤ (m+x k), where m is the size of the graph, matroid, or hyperplane arrangement. It extends Whitney's sign-alternating theorem, Meredith's upper bound theorem, and Dowling and Wilson's lower bound theorem on the coefficient sequence. In the end, we also propose a problem on the combinatorial interpretation of the above inequality. [ABSTRACT FROM AUTHOR]

Let G=(V,E) be a simple graph with V={1,2,...,n} and χ(G,x) be its chromatic polynomial. For an ordering π=(v1,v2,...,vn) of elements of V, let δG(π) be the number of integers i, where 1≤i≤n−1, with either vi

The dimension of a poset P is the minimum number of total orders whose intersection is P. We prove that the dimension of every poset whose comparability graph has maximum degree Δ is at most Δ log{1+o(1) Δ. This result improves on a 30-year old bound of Füredi and Kahn and is within a logo(1) Δ factor of optimal. We prove this result via the notion of boxicity. The boxicity of a graph G is the minimum integer d such that G is the intersection graph of d-dimensional axis-aligned boxes. We prove that every graph with maximum degree Δ has boxicity at most Δ log1+o(1) Δ , which is also within a logo(1) Δ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus g is Θ (√g log g), which solves an open problem of Esperet and Joret and is tight up to a constant factor. [ABSTRACT FROM AUTHOR]

An equitable colouring of a graph G is a vertex colouring where no two adjacent vertices are coloured the same and, additionally, the colour class sizes differ by at most 1. The equitable chromatic number χ = (G) is the minimum number of colours required for this. We study the equitable chromatic number of the dense random graph G(n,m) where m = ⌊p(n 2)⌋ and 0 < p < 0.86 is constant. It is a well-known question of Bollobás [3] whether for p = 1/2 there is a function ƒ(n) → ∞ such that, for any sequence of intervals of length ƒ(n), the normal chromatic number of G(n,m) lies outside the intervals with probability at least 1/2 if n is large enough. Bollobás proposes that this is likely to hold for ƒ(n) = log n. We show that for the equitable chromatic number, the answer to the analogous question is negative. In fact, there is a subsequence (nj)j ∈ N of the integers where χ= (G(nj,mj)) is concentrated on exactly one explicitly known value. This constitutes surprisingly narrow concentration since in this range the equitable chromatic number, like the normal chromatic number, is rather large in absolute value, namely asymptotically equal to n/(2logbn) where b = 1/(1 − p). [ABSTRACT FROM AUTHOR]

While much attention has been directed to the maximum modulus and maximum real part of chromatic roots of graphs of order n (ie, with n vertices), relatively little is known about the maximum imaginary part of such graphs. We prove that the maximum imaginary part can grow linearly in the order of the graph. We also show that for any fixed p∈(0,1), almost every random graph G in the Erdös‐Rényi model has a nonreal root. [ABSTRACT FROM AUTHOR]

The Tutte polynomial is a fundamental invariant of graphs. In this article, we define and study a generalization of the Tutte polynomial for directed graphs, that we name the B-polynomial. The B -polynomial has three variables, but when specialized to the case of graphs (that is, digraphs where arcs come in pairs with opposite directions), one of the variables becomes redundant and the B -polynomial is equivalent to the Tutte polynomial. We explore various properties, expansions, specializations, and generalizations of the B -polynomial, and try to answer the following questions: • what properties of the digraph can be detected from its B -polynomial (acyclicity, length of directed paths, number of strongly connected components, etc.)? • which of the marvelous properties of the Tutte polynomial carry over to the directed graph setting? The B -polynomial generalizes the strict chromatic polynomial of mixed graphs introduced by Beck, Bogart and Pham. We also consider a quasisymmetric function version of the B -polynomial which simultaneously generalizes the Tutte symmetric function of Stanley and the quasisymmetric chromatic function of Shareshian and Wachs. [ABSTRACT FROM AUTHOR]

A strong edge-colouring of an undirected graph G is an edge-colouring where every two edges at distance at most2 receive distinct colours. The strong chromatic index of G is the least number of colours in a strong edge-colouring of G. A conjecture of Erdös and Nešetřil, stated back in the 80's, asserts that every graph with maximum degree Δ should have strong chromatic index at most roughly 1.25Δ2. Several works in the last decades have confirmed this conjecture for various graph classes. In particular, lots of attention have been dedicated to planar graphs, for which the strong chromatic index decreases to roughly 4Δ, and even to smaller values under additional structural requirements. In this work, we initiate the study of the strong chromatic index of 1-planar graphs, which are those graphs that can be drawn on the plane in such a way that every edge is crossed at most once. We provide constructions of 1-planar graphs with maximum degree~Δ and strong chromatic index roughly 6Δ. As an upper bound, we prove that the strong chromatic index of a 1-planar graph with maximum degree Δ is at most roughly 24Δ (thus linear in Δ). The proof of this result is based on the existence of light edges in 1-planar graphs with minimum degree at least 3 [ABSTRACT FROM AUTHOR]

In the eternal domination game, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices and no more than one guard may occupy a vertex. The goal is to determine the eternal domination number of a graph which is the minimum number of guards required to defend the graph against an infinite sequence of attacks. In this paper, we continue the study of the eternal domination game on strong grids. Cartesian grids have been vastly studied with tight bounds for small grids such as 2×n, 3×n, 4×n, and 5×n grids, and recently it was proven in [Lamprou et al., CIAC 2017, 393-404] that the eternal domination number of these grids in general is within O(m+n) of their domination number which lower bounds the eternal domination number. Recently, Finbow et al. proved that the eternal domination number of strong grids is upper bounded by mn6+O(m+n). We adapt the techniques of [Lamprou et al., CIAC 2017, 393-404] to prove that the eternal domination number of strong grids is upper bounded by mn7+O(m+n). While this does not improve upon a recently announced bound of ⌈m3⌉⌈n3⌉+O(mn--√) [Mc Inerney, Nisse, Pérennes, CIAC 2019] in the general case, we show that our bound is an improvement in the case where the smaller of the two dimensions is at most 6179. [ABSTRACT FROM AUTHOR]

For any r -uniform hypergraph H with m (≥2) edges, let P (H , k) and P l (H , k) be the chromatic polynomial and the list-color function of H respectively, and let ρ (H) denote the minimum value of | e ∖ e ′ | among all pairs of distinct edges e , e ′ in H. We will show that if r ≥ 3 , ρ (H) ≥ 2 and m ≥ ρ (H) 3 2 + 1 , then P l (H , k) = P (H , k) holds for all integers k ≥ 2.4 (m − 1) ρ (H) log ⁡ (m − 1). [ABSTRACT FROM AUTHOR]

Trees are generalized to a special kind of higher dimensional complexes known as \((j,k)\)-trees ([L. W. Beineke, R. E. Pippert, On the structure of \((m,n)\)-trees, Proc. 8th S-E Conf. Combinatorics, Graph Theory and Computing, 1977, 75-80]), and which are a natural extension of \(k\)-trees for \(j=k-1\). The aim of this paper is to study\((k-r,k)\)-trees ([H. P. Patil, Studies on \(k\)-trees and some related topics, PhD Thesis, University of Warsaw, Poland, 1984]), which are a generalization of \(k\)-trees (or usual trees when \(k=1\)). We obtain the chromatic polynomial of \((k-r,k)\)-trees and show that any two \((k-r,k)\)-trees of the same order are chromatically equivalent. However, if \(r\neq 1\) in any \((k-r,k)\)-tree \(G\), then it is shown that there exists another chromatically equivalent graph \(H\), which is not a \((k-r,k)\)-tree. Further, the vertex-partition number and generalized total colourings of \((k-r,k)\)-trees are obtained. We formulate a conjecture about the chromatic index of \((k-r,k)\)-trees, and verify this conjecture in a number of cases. Finally, we obtain a result of [M. Borowiecki, W. Chojnacki, Chromatic index of \(k\)-trees, Discuss. Math. 9 (1988), 55-58] as a corollary in which \(k\)-trees of Class 2 are characterized.

We study the list chromatic number of the Cartesian product of any graph G and a complete bipartite graph with partite sets of size a and b, denoted χ ℓ (G □ K a , b) . We have two motivations. A classic result on the gap between list chromatic number and the chromatic number tells us χ ℓ (K a , b) = 1 + a if and only if b ≥ a a . Since χ ℓ (K a , b) ≤ 1 + a for any b ∈ N , this result tells us the values of b for which χ ℓ (K a , b) is as large as possible and far from χ (K a , b) = 2 . In this paper we seek to understand when χ ℓ (G □ K a , b) is far from χ (G □ K a , b) = max { χ (G) , 2 } . It is easy to show χ ℓ (G □ K a , b) ≤ χ ℓ (G) + a . Borowiecki et al. (Discrete Math 306:1955–1958, 2006) showed that this bound is attainable if b is sufficiently large; specifically, χ ℓ (G □ K a , b) = χ ℓ (G) + a whenever b ≥ (χ ℓ (G) + a - 1) a | V (G) | . Given any graph G and a ∈ N , we wish to determine the smallest b such that χ ℓ (G □ K a , b) = χ ℓ (G) + a . In this paper we show that the list color function, a list analogue of the chromatic polynomial, provides the right concept and tool for making progress on this problem. Using the list color function, we prove a general improvement on Borowiecki et al.'s (2006) result, and we compute the smallest such b for some large families of chromatic-choosable graphs. [ABSTRACT FROM AUTHOR]

Let m , n , λ be positive integers. What is the maximum number of proper vertex colorings in (at most) λ colors a graph with n vertices and m edges can have? On which graphs is this maximum attained? The question can be rephrased as the one of maximizing χ (G , λ) , the value of the chromatic polynomial of G at λ , over all graphs G with n vertices and m edges. This problem was stated independently by Wilf and Linial, and is still unsolved. In this article we survey the current state of the research directed at solving the problem. [ABSTRACT FROM AUTHOR]

Let G be a finite group and let r ∈ ℕ. An r -coloring of G is any mapping χ : G → { 1 , ... , r }. A coloring χ is symmetric if there is g ∈ G such that χ (g x − 1 g) = χ (x) for every x ∈ G. We show that if G is Abelian and f (r) is the polynomial representing the number of symmetric r -colorings of G , then the number of symmetric r -colorings of G × ℤ 2 is f (r 2). We also extend this result to the dihedral group D (G). [ABSTRACT FROM AUTHOR]

The pioneering work of Jones and Kauffman unveiled a fruitful relationship between statistical mechanics and knot theory. Recently, Jones introduced two subgroups F → and T → of the Thompson groups F and T, respectively, together with a procedure that associates an oriented link diagram to any element of these subgroups. Moreover, several specializations of some well-known polynomial link invariants can be seen as functions of positive type on the Thompson groups or the Jones–Thompson subgroups. One important example is provided by suitable evaluations of the Jones polynomial, which are thus associated with certain unitary representations of the groups F → and T → . Within this framework, we discuss an alternative approach that relies on some partition function interpretation of the Jones polynomial, and also exhibit more examples associated with other link invariants, notably the two-variable Kauffman polynomial and the HOMFLY polynomial. In the unoriented case, extending our previous results, we also show by similar methods that certain evaluations of the Tutte polynomial and of the Kauffman bracket, suitably renormalized, yield functions of positive type on T. [ABSTRACT FROM AUTHOR]

We construct a new polynomial invariant for signed graphs, the trivari- ate Tutte polynomial, which contains among its evaluations the number of proper colorings and the number of nowhere-zero flows. In this, it parallels the Tutte poly- nomial of a graph, which contains the chromatic polynomial and flow polynomial as specializations. While the Tutte polynomial of a graph is equivalently defined as the dichromatic polynomial or Whitney rank polynomial, the dichromatic polynomial of a signed graph (defined more widely for biased graphs by Zaslavsky) does not, by contrast, give the number of nowhere-zero flows as an evaluation in general. The trivariate Tutte polynomial contains Zaslavsky's dichromatic polynomial as a spe- cialization. Furthermore, the trivariate Tutte polynomial gives as an evaluation the number of proper colorings of a signed graph under a more general sense of signed graph coloring in which colors are elements of an arbitrary finite set equipped with an involution. [ABSTRACT FROM AUTHOR]

Tracking objects is an important field for many applications like driving assistance and video surveillance. Every tracking system should be able to track objects in complex scenes. One of the most challenging problems is tracking of objects undergoing an occlusion. Indeed, several tracking systems suffer from lack of information to accomplish the tracking task when two or many objects are in occlusion. To address this issue, this paper presents a novel approach combining fuzzy logic with chromatic co-occurrence matrices in order to develop a robust tracking method that is able to determine the target position more accurately during an illumination variation or an occlusion situation. The qualitative and quantitative studies on challenging sequences demonstrate that the results obtained by the proposed algorithm are very competitive in comparison with several state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Let G be a threshold graph. In this paper, we give, in first hand, a formula relating the chromatic polynomial of G (the complement of G) to the chromatic polynomial of G: In second hand, we express the chromatic polynomials of G and G in terms of the generalized Bell polynomials. [ABSTRACT FROM AUTHOR]

We give the Jones polynomial of the alternating links that correspond to a family of positive-signed connected planar graphs. We first find the general form of the Tutte polynomial of the family of graphs and then specializes it to the Jones polynomial. Then we recover the flow and chromatic polynomials from it as special cases. Finally, we give useful combinatorial information about the graph by evaluating the Tutte polynomial at some special points. [ABSTRACT FROM AUTHOR]

Coloring of fuzzy graphs has many real life applications in combinatorial optimization problems like traffic light system, exam scheduling, register allocation, etc. In this paper, the concept of fuzzy chromatic polynomial of fuzzy graph is introduced and defined based on α-cuts of fuzzy graph. Two different types of fuzziness to fuzzy graph are considered in the paper. The first type was fuzzy graph with crisp vertex set and fuzzy edge set and the second type was fuzzy graph with fuzzy vertex set and fuzzy edge set. Depending on this, the fuzzy chromatic polynomials for some fuzzy graphs are discussed. Some interesting remarks on fuzzy chromatic polynomial of fuzzy graphs have been derived. Further, some results related to the concept are proved. Lastly, fuzzy chromatic polynomials for complete fuzzy graphs and fuzzy cycles are studied and some results are obtained. [ABSTRACT FROM AUTHOR]

Abstract Minimization of energy in gradient systems leads to formation of oscillatory and Turing patterns in reaction-diffusion systems. These patterns should be accurately computed using fine space and time meshes over long time horizons to reach the spatially inhomogeneous steady state. In this paper, a reduced order model (ROM) is developed which preserves the gradient dissipative structure. The coupled system of reaction-diffusion equations are discretized in space by the symmetric interior penalty discontinuous Galerkin (SIPG) method. The resulting system of ordinary differential equations (ODEs) are integrated in time by the average vector field (AVF) method, which preserves the energy dissipation of the gradient systems. The ROMs are constructed by the proper orthogonal decomposition (POD) with Galerkin projection. The nonlinear reaction terms are computed efficiently by discrete empirical interpolation method (DEIM). Preservation of the discrete energy of the FOMs and ROMs with POD-DEIM ensures the long term stability of the steady state solutions. Numerical simulations are performed for the gradient dissipative systems with two specific equations; real Ginzburg–Landau equation and Swift–Hohenberg equation. Numerical results demonstrate that the POD-DEIM reduced order solutions preserve well the energy dissipation over time and at the steady state. [ABSTRACT FROM AUTHOR]

Abstract We present an approach to the factorization method for second order difference equations on time scales. We construct Hilbert spaces of functions on the time scale and show how to construct a chain of intertwined first order Δ-difference operators A k in the sense that A k and A k * act as ladder operators generating new solutions of eigenproblem of A k A k *. [ABSTRACT FROM AUTHOR]

Abstract The generalized k -connectivity κ k (G) of a graph G is a generalization of the concept of the traditional connectivity, which can serve for measuring the capability of a graph G to connect any k vertices in G. In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph μ (G), which is called the Mycielskian of G. In this paper, we investigate the relation between the generalized 3-connectivity of the Mycielskian of a graph G and the generalized 3-connectivity of G , and show that κ 3 (μ (G)) ≥ κ 3 (G) + 1. Moreover, by this result, we completely determine the generalized 3-connectivity of the Mycielskian of the tree T n , the complete graph K n and the complete bipartite graph K a,b. [ABSTRACT FROM AUTHOR]

Let S⊆V . A vertex uϵ V is a dominator of S if v dominates every vertex in S and v is said to be an anti-dominator of S if v dominates none of the vertices of S. Let C = (V1, V2, …, Vk) be a coloring of G and let v ϵ V (G). A color class Vi is called a dom-color class or an anti dom- color class of the vertex v according as v is a dominator of Vi or an anti- dominator of Vi. The coloring C is called a global dominator coloring of G if every vertex of G has a dom-color class and an anti dom-color class in C. The minimum number of colors required for a global dominator coloring of G is called the global dominator chromatic number and is denoted by Xgd(G). This paper initiates a study on this notion of global dominator coloring. [ABSTRACT FROM AUTHOR]

Abstract We study a family of polynomials associated with ascent–descent statistics on labeled rooted plane k -ary trees introduced by Gessel, from a rook-theoretic perspective. We generalize the excedance statistic on permutations to maximal nonattacking rook placements on certain rectangular boards by decomposing them into staircase boards. We then relate the number of maximal nonattacking rook placements on certain skew boards to the number of regions in extended Linial arrangements by establishing a relation between the factorial polynomial of those boards to the characteristic polynomial of extended Linial arrangements. Furthermore, we give a combinatorial interpretation of the number of bounded regions in extended Linial arrangements in terms of certain labeled rooted plane k -ary trees. Finally, using the work of Goldman–Joichi–White, we identify graphs whose chromatic polynomials equal the characteristic polynomials of extended Linial arrangements up to a straightforward normalization. [ABSTRACT FROM AUTHOR]

Let H be a group. The co-maximal graph of H , denoted by Γ (H) , is a graph whose vertices are nontrivial elements of H and two distinct vertices x and y are adjacent in Γ (H) if and only if 〈 x 〉 〈 y 〉 = H. In this paper, we study some connections between the graph-theoretic properties of this graph and some algebraic properties of groups. For instance, we characterized all groups whose co-maximal graphs are connected and we show that if Γ (H) has no isolated vertex, then Γ (H) is connected with diameter at most 2. Moreover, we classify all groups whose co-maximal graphs are complete. Also, some results on the clique number and chromatic number of a co-maximal graph are given. In addition, the co-maximal graphs of abelian groups are studied. [ABSTRACT FROM AUTHOR]

In the paper extended Keller graph is defined and some of its properties, such as Hamiltonian, the independence number, the chromatic number, etc., are proved. Moreover, the size of a maximum clique of for d = 2, 3, 4 and d ≥ 8 is given and for d = 5, 6, 7 a conjecture is stated. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we focus on a special chromatic invariant of graphs, so-called the locating chromatic number. We give a sharp upper bound of the locating chromatic number of trees by using the number of leaves. [ABSTRACT FROM AUTHOR]

Abstract For an undirected graph G , the chromatic polynomial is a key specialisation of its Tutte polynomial. The " (α + n) -conjecture" states that given any algebraic integer α , for large enough n ∈ N the shifted value α + n is the root of some chromatic polynomial. We develop an algorithm whose input is a monic polynomial P d (X) ∈ Z [ X ] of degree d ≤ 4 , and the output is a (d , N) -biclique whose chromatic polynomial is a product of linear factors and the factor P d (X − n) where n ∈ N is taken to be sufficiently large, provided that such a (d , N) -biclique exists. In degree d = 3 our method tends to produce smaller (3 , N) -bicliques than Adam Bohn's cubic parameterisation (Bohn, 2014), while in degree d = 4 it provides an efficient way to check the (α + n) -conjecture for a given quartic polynomial. The construction relies on previous work of Farrell (1980) which interprets chromatic coefficients via induced subgraphs, together with a simple search algorithm that is based on the number of ways to partition an integer. We also derive new expressions for the interesting factors of the chromatic polynomials for (3 , N) -bicliques and (4 , N) -bicliques, in terms of these induced subgraphs. [ABSTRACT FROM AUTHOR]

Abstract A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by one. We consider the problems of deciding whether a graph has a critical vertex or edge, respectively. We give a complexity dichotomy for both problems restricted to H -free graphs, that is, graphs with no induced subgraph isomorphic to H. Moreover, we show that an edge is critical if and only if its contraction reduces the chromatic number by one. Hence, we also obtain a complexity dichotomy for the problem of deciding if a graph has an edge whose contraction reduces the chromatic number by one. [ABSTRACT FROM AUTHOR]

Steinberg and Tovey proved that every n‐vertex planar triangle‐free graph has an independent set of size at least (n+1)∕3, and described an infinite class of tight examples. We show that all n‐vertex planar triangle‐free graphs except for this one infinite class have independent sets of size at least (n+2)∕3. [ABSTRACT FROM AUTHOR]

Abstract We investigate the group irregularity strength, s g (G), of a graph, i.e., the least integer k such that taking any Abelian group G of order k , there exists a function f : E (G) → G so that the sums of edge labels incident with every vertex are distinct. So far the best upper bound on s g (G) for a general graph G was exponential in n − c , where n is the order of G and c denotes the number of its components. In this note we prove that s g (G) is linear in n , namely not greater than 2 n. In fact, we prove a stronger result, as we additionally forbid the identity element of a group to be an edge label or the sum of labels around a vertex. We consider also locally irregular labelings where we require only sums of adjacent vertices to be distinct. For the corresponding graph invariant we prove the general upper bound: Δ (G) + col (G) − 1 (where col(G) is the coloring number of G) in the case when we do not use the identity element as an edge label, and a slightly worse one if we additionally forbid it as the sum of labels around a vertex. In the both cases we also provide a sharp upper bound for trees and a constant upper bound for the family of planar graphs. [ABSTRACT FROM AUTHOR]