Maxmaxflow and counting subgraphs

Bill Jackson, Alan D. Sokal

    Research output: Contribution to journalArticle

    Abstract

    We introduce a new graph invariant Λ(G) that we call maxmaxflow, and put it in the context of some other well-known graph invariants, notably maximum degree and its relatives. We prove the equivalence of two "dual" definitions of maxmaxflow: one in terms of flows, the other in terms of cocycle bases. We then show how to bound the total number (or more generally, total weight) of various classes of subgraphs of G in terms of either maximum degree or maxmaxflow. Our results are motivated by a conjecture that the modulus of the roots of the chromatic polynomial of G can be bounded above by a function of Λ(G).

    Original languageEnglish (US)
    Pages (from-to)1-46
    Number of pages46
    JournalElectronic Journal of Combinatorics
    Volume17
    Issue number1
    DOIs
    StatePublished - 2010

    Keywords

    • Chromatic polynomial
    • Cocycle
    • Degeneracy number
    • Flow
    • Graph
    • Maximum degree
    • Maxmaxflow
    • Second-largest degree
    • Subgraph

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Discrete Mathematics and Combinatorics
    • Computational Theory and Mathematics
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Maxmaxflow and counting subgraphs'. Together they form a unique fingerprint.

  • Cite this