Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Broken-cycle-free subgraphs and the log-concavity conjecture for chromatic polynomials
KTH, School of Engineering Sciences (SCI), Theoretical Physics, Condensed Matter Theory.
2006 (English)In: Experimental Mathematics, ISSN 1058-6458, E-ISSN 1944-950X, Vol. 15, no 3, 343-353 p.Article in journal (Refereed) Published
Abstract [en]

This paper concerns the coefficients of the chromatic polynomial of a graph. We first report on a computational verification of the strict log-concavity conjecture for chromatic polynomials for all graphs on at most 11 vertices, as well as for certain cubic graphs. In the second part of the paper we give a number of conjectures and theorems regarding the behavior of the coefficients of the chromatic polynomial, in part motivated by our computations. Here our focus is on epsilon(G), the average size of a broken-cycle-free subgraph of the graph G, whose behavior under edge deletion and contraction is studied.

Place, publisher, year, edition, pages
2006. Vol. 15, no 3, 343-353 p.
Keyword [en]
chromatic polynomial, log-concavity, subgraphs, bounds
Identifiers
URN: urn:nbn:se:kth:diva-16095ISI: 000241619800006Scopus ID: 2-s2.0-33750885391OAI: oai:DiVA.org:kth-16095DiVA: diva2:334137
Note
QC 20100525Available from: 2010-08-05 Created: 2010-08-05Bibliographically approved

Open Access in DiVA

No full text

Scopus

Search in DiVA

By author/editor
Lundow, Per Håkan
By organisation
Condensed Matter Theory
In the same journal
Experimental Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 33 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf