Maxmaxflow and counting subgraphs (Q986701)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maxmaxflow and counting subgraphs |
scientific article |
Statements
Maxmaxflow and counting subgraphs (English)
0 references
12 August 2010
0 references
Summary: We introduce a new graph invariant \(\Lambda (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 \(\Lambda (G)\).
0 references
graph
0 references
subgraph
0 references
flow
0 references
cocycle
0 references
maxmaxflow
0 references
maximum degree
0 references
secondlargest degree
0 references
degeneracy number
0 references
chromatic polynomial
0 references