TITLE

A new two-variable generalization of the chromatic polynomial

AUTHOR(S)
Dohmen, Klaus; Pönitz, André; Tittmann, Peter
PUB. DATE
June 2003
SOURCE
Discrete Mathematics & Theoretical Computer Science (DMTCS);Jun2003, Vol. 6 Issue 1, p69
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
Let P(G;x,y) be the number of vertex colorings Φ : V → {1,...,x} of an undirected graph G = (V,E) such that for all edges {u,v} ∈ E the relations Φ(u) ≤ y and Φ(v) ≤ y imply Φ(u) ≠ Φ(v). We show that P(G;x,y) is a polynomial in x and y which is closely related to Stanley's chromatic symmetric function, and which simultaneously generalizes the chromatic polynomial, the independence polynomial, and the matching polynomial of G. We establish two general expressions for this new polynomial: one in terms of the broken circuit complex, and one in terms of the lattice of forbidden colorings. Finally, we give explicit expressions for the generalized chromatic polynomial of complete graphs, complete bipartite graphs, paths, and cycles, and show that P(G;x, y) can be evaluated in polynomial time for trees and graphs of restricted pathwidth.
ACCESSION #
11345614

 

Related Articles

  • DICHOTOMY AND POSITIVITY OF NEUTRAL EQUATIONS WITH NONAUTONOMOUS PAST. Huy, Nguyen Thieu; Bang, Pham Van // Applicable Analysis & Discrete Mathematics;2014, Vol. 8 Issue 2, p224 

    Consider the linear partial neutral functional differential equations with nonautonomous past of the form ∂/∂t F(u(t, •)) = BFu(t, •) + Φu(t, •), t ≥ 0, ∂/∂t u(t, s) = ∂/∂s-u(t, s) + A(s)u(t, s), t ≥ 0 ≥ s, where the function...

  • Multiple solutions of ordinary differential systems with min-max terms and applications to the fuzzy differential equations. Liu, Yicheng; Wu, Jun // Advances in Difference Equations;12/18/2015, Vol. 2015 Issue 1, p1 

    In this paper, we investigate the existence of multiple solutions for a class of ordinary differential systems with min-max terms. We present two fundamental results for the existence of solutions. An illustrative example shows that the uniqueness of solution does not hold although the Lipschitz...

  • Padé Approximants in Complex Points Revisited. Hebhoub, Fahima; Yushchenko, Lidiya // International Journal of Mathematics & Mathematical Sciences;2011, p1 

    The class of complex symmetric functions contains the Stieltjes functions. The aim of this work is to give some new results concerning the location of zeros and poles of Padé approximants using the Taylor series of functions developed in neighborhoods of complex points and their conjugate points.

  • Chromatic Polynomials and the Symmetric Group. Philippe Pitteloud // Graphs & Combinatorics;Mar2004, Vol. 20 Issue 1, p131 

    In this paper we give first a new combinatorial interpretation of the coefficients of chromatic polynomials of graphs in terms of subsets of permutations. Motivated by this new interpretation, we introduce next a combinatorially defined polynomial associated to a directed graph, and prove that...

  • MONOCHROMATIC CYCLES AND MONOCHROMATIC PATHS IN ARC-COLORED DIGRAPHS. GALEANA-SÁNCHEZ, HORTENSIA; GAYTÁN-GÓMEZ, GUADALUPE; ROJAS-MONROY, ROCÍO // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 2, p283 

    No abstract available.

  • Theoretic properties of the symmetric algebra of edge ideals. Imbesi, Maurizio; La Barbiera, Monica // Bulletin of the Belgian Mathematical Society - Simon Stevin;May2015, Vol. 22 Issue 2, p331 

    In this note the integrality and the reducedness for the symmetric algebra of the edge ideals of simple graphs are analyzed. More precisely, we will extend a result on the integrality of the symmetric algebra given for connected graphs, stating a characterization for any simple graph. Moreover,...

  • A new two-variable generalization of the chromatic polynomial. Dohmen, Klaus; Pönitz, André; Tittmann, Peter // Discrete Mathematics & Theoretical Computer Science (DMTCS);Dec2003, Vol. 6 Issue 2, p69 

    Let P(G; x; y) be the number of vertex colorings &phi : V → {1,...,x} of an undirected graph G = (V, E) such that for all edges { u, v} ≠ E the relations &phi(v) ≤ y and φ(v) ≤ y implyφ(u) ≠ φ(v). We show that P(G; x, y) is a polynomial in x and y which...

  • The Christoffel-Minkowski problem I: Convexity of solutions of a Hessian equation. Guan, Pengfei; Ma, Xi-Nan // Inventiones Mathematicae;Mar2003, Vol. 151 Issue 3, p553 

    Surface area measures are local versions of quermassintegrals in the theory of convex bodies. If the boundary of the convex body is smooth, the corresponding surface area function is a symmetric function of the principal radii of its boundary. The general problem of finding a convex hypersurface...

  • Properties of the Zeros of the Polynomials Belonging to the Askey Scheme. Bihun, Oksana; Calogero, Francesco // Letters in Mathematical Physics;Dec2014, Vol. 104 Issue 12, p1571 

    In this paper, we provide properties-which are, to the best of our knowledge, new-of the zeros of the polynomials belonging to the Askey scheme. These findings include Diophantine relations satisfied by these zeros when the parameters characterizing these polynomials are appropriately restricted.

Share

Read the Article

Courtesy of VIRGINIA BEACH PUBLIC LIBRARY AND SYSTEM

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics