Results 51 to 60 of about 759 (82)
Intersections of circuits and cocircuits in binary matroids
Discrete Mathematics, 1999 Oxley has shown that if, for some \(k\geq 4\), a matroid \(M\) has a \(k\)-element set that is the intersection of a circuit and cocircuit, then \(M\) has a 4-element set that is the intersection of a circuit and a cocircuit. In the paper, it is proved that, under the above hypothesis, for \(k\geq 6\), a binary matroid also has a 6-element set that is ...
openaire +1 more source
A characterization of graphic matroids using non-separating cocircuits
Advances in Applied Mathematics, 2009 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +1 more source
Non-Separating Cocircuits and Graphicness in Matroids
, 2012 Let $M$ be a 3-connected binary matroid and let $Y(M)$ be the set of elements of $M$ avoiding at least $r(M)+1$ non-separating cocircuits of $M$. Lemos proved that $M$ is non-graphic if and only if $Y(M)\neq\emp$. We generalize this result when by establishing that $Y(M)$ is very large when $M$ is non-graphic and $M$ has no $M\s(K_{3,3}"')$-minor if $M$
openaire +3 more sources
Counting cocircuits and convex two-colourings is #P-complete
, 2008 We prove that the problem of counting the number of colourings of the vertices of a graph with at most two colours, such that the colour classes induce connected subgraphs is #P-complete. We also show that the closely related problem of counting the number of cocircuits of a graph is #P-complete.
openaire +1 more source
Contracting an element from a cocircuit [PDF]
Advances in Applied Mathematics, 2008 For the abstract of this paper, please see the PDF ...
Dillon Mayhew, Rhiannon Hall
exaly +7 more sources
Matroids with an infinite circuit–cocircuit intersection
Journal of Combinatorial Theory Series B, 2014 We construct some matroids that have a circuit and a cocircuit with infinite intersection. This answers a question of Bruhn, Diestel, Kriesell, Pendavingh and Wollan. It further shows that the axiom system for matroids proposed by Dress does not axiomatize all infinite matroids.
Johannes Carmesin
exaly +4 more sources
Cubic time recognition of cocircuit graphs of uniform oriented matroids
European Journal of Combinatorics, 2011 We present an algorithm which takes a graph as input and decides in cubic time if the graph is the cocircuit graph of a uniform oriented matroid. In the affirmative case the algorithm returns the set of signed cocircuits of the oriented matroid. This improves an algorithm proposed by Babson, Finschi and Fukuda.
Kolja Knauer, Juan, Ricardo Strausz
exaly +3 more sources
Extending a matroid by a cocircuit
Discrete Mathematics, 2006 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Joseph E Bonin
exaly +3 more sources
Some of the next articles are maybe not open access.
Nonseparating Cocircuits in Binary Matroids
SIAM Journal on Discrete Mathematics, 2021New methods on nonseparating cocircuits in binary matroids are presented and each lead to efficient algorithms which are discussed in detail. The author extends robust work introduced by Tutte and further developed by Oxley, Iri, and Kelmans (among others).
openaire +2 more sources
Simple Matroids with Bounded Cocircuit Size
Combinatorics, Probability and Computing, 2000The simple observation that a graph on \(2n\) vertices, each of which has degree at most \(d\), can have at most \(nd\) edges is generalized in the paper under review to matroids, where \(d\) becomes the cocircuit size and the role of the vertices is replaced by the rank of the matroid.
Bonin, Joseph E., Reid, Talmage James
openaire +2 more sources