The roots of the independence polynomial of a clawfree graph

DOI10.1016/j.jctb.2006.06.001zbMath1119.05075OpenAlexW2096626276MaRDI QIDQ875937

Maria Chudnovsky, P. D. Seymour

Publication date: 16 April 2007

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2006.06.001

zbMATH Keywords

real rootsindependence polynomialclawfree graphs

Mathematics Subject Classification ID

Real polynomials: location of zeros (26C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Interview with Carla D. Savage, \((M,i)\)-multiset Eulerian polynomials, General position polynomials, Independence Equivalence Classes of Paths and Cycles, Properties of chromatic polynomials of hypergraphs not held for chromatic polynomials of graphs, On the roots of total domination polynomial of graphs, Clique cover products and unimodality of independence polynomials, Approximating real-rooted and stable polynomials, with combinatorial applications, Analytic properties of sextet polynomials of hexagonal systems, Unimodality of independence polynomials of the incidence product of graphs, Building graphs whose independence polynomials have only real roots, Interlacing families. III: Sharper restricted invertibility estimates, Matroid representation of clique complexes, Descent generating polynomials and the Hermite-Biehler theorem, Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes, Concentration inequalities for ultra log-concave distributions, Inertia indices and eigenvalue inequalities for Hermitian matrices, Multicomplexes and polynomials with real zeros, On the Roots of Expected Independence Polynomials, Upper tails and independence polynomials in random graphs, Maximum modulus of independence roots of graphs and trees, On the unimodality of independence polynomials of some graphs, Log-concavity, ultra-log-concavity, and a maximum entropy property of discrete compound Poisson measures, A bound on the values of independence polynomials at \(-1/k\) for \(k\)-degenerate graphs, Unimodality of independence polynomials of the cycle cover product of graphs, On the unimodality of domination polynomials, Brenti's Open Problem on the Real-Rootedness of $q$-Eulerian Polynomials of Type $D$, Derivation of the real-rootedness of coordinator polynomials from the Hermite-Biehler theorem, Absence of zeros implies strong spatial mixing, Combinatorics. Abstracts from the workshop held January 1--7, 2023, Network reliability: Heading out on the highway, Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials, On real-rootedness of independence polynomials of rooted products of graphs, Co-2-plex polynomials, Mehler formulae for matching polynomials of graphs and independence polynomials of clawfree graphs, Independence polynomials of some compound graphs, The roller-coaster conjecture revisited, Several improved asymptotic normality criteria and their applications to graph polynomials, Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, On the unimodality of independence polynomials of very well-covered graphs, Some results on the independence polynomial of unicyclic graphs, Two problems on independent sets in graphs, The independent set sequence of regular bipartite graphs, Four deviations suffice for rank 1 matrices, Inapproximability of the Independent Set Polynomial in the Complex Plane, On the independent domination polynomial of a graph, Graphs whose independence fractals are line segments, Hoste’s conjecture for generalized Fibonacci polynomials, Graphs with a minimal number of convex sets, Some applications of Wagner's weighted subgraph counting polynomial, Recurrences for Eulerian polynomials of type B and type D, Approximating permanents and hafnians, A unified proof of interlacing properties of eigenvalues of totally positive matrices, Free fermions behind the disguise, Acyclic polynomials of graphs, On the roots of independence polynomials of almost all very well-covered graphs, On the stability of independence polynomials, Lee-Yang theorems and the complexity of computing averages, The converse of Weyl's eigenvalue inequality, Some conjectures on the zeros of approximates to the Riemann \(\Xi\)-function and incomplete gamma functions, A simple proof of an inequality connecting the alternating number of independent sets and the decycling number, A note on purely imaginary independence roots, The independence polynomial of rooted products of graphs, Log-concavity of independence polynomials of some kinds of trees, Independence polynomials of \(k\)-tree related graphs, The \(f\)- and \(h\)-vectors of interval subdivisions, On the coefficients of the independence polynomial of graphs, On the Charney-Davis and Neggers-Stanley conjectures, On the roots of domination polynomials, A logician's view of graph polynomials, Counting independent sets in graphs with bounded bipartite pathwidth, The independent set sequence of some families of trees, On the roots of strongly connected reliability polynomials, Matchings in Benjamini–Schramm convergent graph sequences, On the roots of Wiener polynomials of graphs, On a conjecture of Sokal concerning roots of the independence polynomial, Independence polynomials and Alexander-Conway polynomials of plumbing links, On the largest eigenvalue of a mixed graph with partial orientation, On trees with real-rooted independence polynomial, The mathematics of lecture hall partitions, Christoffel–Darboux Type Identities for the Independence Polynomial, On the Roots of σ-Polynomials, Unimodality of independence polynomials of rooted products of graphs, On the independent set sequence of a tree, Unimodality of the independence polynomials of non-regular caterpillars, Semantic Equivalence of Graph Polynomials Definable in Second Order Logic, Complexes of directed trees and independence complexes, On the growth of deviations, Subset selection for matrices with fixed blocks, Matchings and squarefree powers of edge ideals, The 𝐬-Eulerian polynomials have only real roots, Counting Weighted Independent Sets beyond the Permanent, Generalizations of the matching polynomial to the multivariate independence polynomial, Independence polynomials of bipartite graphs, Unimodality of the independence polynomials of some composite graphs, Spectrahedrality of hyperbolicity cones of multivariate matching polynomials, Some families of graphs with no nonzero real domination roots, Graded Lie algebras of type FP, Almost unimodal and real-rooted graph polynomials, On the unimodality of average edge cover polynomials, Interlacing families. I: Bipartite Ramanujan graphs of all degrees, Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem

Cites Work

• On the location of roots of independence polynomials
• Root locations of an entire polytope of polynomials: It suffices to check the edges
• Obreschkoff's theorem revisited: What convex sets are contained in the set of hyperbolic polynomials?
• Corrigendum: Obreschkoff's theorem revisited: What convex sets are contained in the set of hyperbolic polynomials?
• Clique polynomials and independent set polynomials of graphs
• Roots of independence polynomials of well covered graphs
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• Average independence polynomials
• On the numbers of independent \(k\)-sets in a claw free graph
• Theory of monomer-dimer systems
• Dependence polynomials
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item