Recursion relations for chromatic coefficients for graphs and hypergraphs

Durhuus, Bergfinnur and Lucia, Angelo (2019) Recursion relations for chromatic coefficients for graphs and hypergraphs. Discussiones Mathematicae Graph Theory, 42 (1). pp. 101-121. ISSN 1234-3099. doi:10.7151/dmgt.2248. https://resolver.caltech.edu/CaltechAUTHORS:20220127-789177900

	PDF - Published Version See Usage Policy. 211kB
	PDF - Accepted Version See Usage Policy. 221kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220127-789177900

Abstract

We establish a set of recursion relations for the coefficients in the chromatic polynomial of a graph or a hypergraph. As an application we provide a generalization of Whitney's broken cycle theorem for hypergraphs, as well as deriving an explicit formula for the linear coefficient of the chromatic polynomial of the -complete hypergraph in terms of roots of the Taylor polynomials for the exponential function.

Item Type:

Article

Related URLs:

URL	URL Type	Description
https://doi.org/10.7151/dmgt.2248	DOI	Article
https://arxiv.org/abs/1901.00899	arXiv	Discussion Paper

ORCID:

Author	ORCID
Durhuus, Bergfinnur	0000-0002-0450-6792
Lucia, Angelo	0000-0003-1709-1220

Additional Information:

© 2022 University of Zielona Góra. Received: 2019-03-25, Revised: 2019-07-06, Accepted: 2019-07-31, Available online: 2019-11-18. The authors acknowledge support from the Villum Foundation via the QMATH Centre of Excellence (Grant no. 19959). A.L. acknowledges support from the Walter Burke Institute for Theoretical Physics in the form of the Sherman Fairchild Fellowship as well as support from the Institute for Quantum Information and Matter (IQIM), an NSF Physics Frontiers Center (NFS Grant PHY-1733907).

Group:

Institute for Quantum Information and Matter, Walter Burke Institute for Theoretical Physics

Funders:

Funding Agency	Grant Number
Villum Foundation	19959
Walter Burke Institute for Theoretical Physics, Caltech	UNSPECIFIED
Sherman Fairchild Foundation	UNSPECIFIED
Institute for Quantum Information and Matter (IQIM)	UNSPECIFIED
NSF	PHY-1733907

Subject Keywords:

chromatic polynomials, hypergraphs, broken cycles

Issue or Number:

DOI:

10.7151/dmgt.2248

Record Number:

CaltechAUTHORS:20220127-789177900

Persistent URL:

https://resolver.caltech.edu/CaltechAUTHORS:20220127-789177900

Usage Policy:

No commercial reproduction, distribution, display or performance rights in this work are provided.

ID Code:

113132

Collection:

CaltechAUTHORS

Deposited By:

Tony Diaz

Deposited On:

28 Jan 2022 19:03

Last Modified:

28 Jan 2022 19:03

Repository Staff Only: item control page