BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Steven D. Noble contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
The Merino-Welsh conjecture asserts that the number of spanning trees of a graph is no greater than the maximum of the numbers of totally cyclic orientations and acyclic orientations of that graph. We prove this conjecture for the class of series-parallel graphs.
A mapping from the vertex set of a graph G = (V,E) into an interval of integers {0,...,k} is an L(2,1)-labelling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbour are mapped onto distinct integers. It is known that for any fixed k >= 4, deciding the existence of such a labelling is an NP-complete problem while it is polynomial for k <= 3. For even k >= 8, it remains NP-complete when restricted to planar graphs. In this paper, we show that it remains NP-complete for any k >= 4 by reduction from Planar Cubic Two-Colourable Perfect Matching. Schaefer stated without proof that Planar Cubic Two-Colourable Perfect Matching is NP-complete. In this paper we give a proof of this.
We give two proofs that the $h$-vector of any paving matroid is a pure O-sequence, thus answering in the affirmative a conjecture made by R. Stanley, for this particular class of matroids. We also investigate the problem of obtaining good lower bounds for the number of bases of a paving matroid given its rank and number of elements.