A parity result of Fraysseix, computational complexity of Tutte polynomials, and a conjecture on planar graphs

DOI10.1016/J.ENDM.2008.06.024MaRDI QIDQ5300994zbMATH OpenOpenAlexWikidataFDO

Authors Michel Las Vergnas

Publication date 28 June 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2008.06.024

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph polynomials (05C31) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• The Computational Complexity of Tutte Invariants for Planar Graphs
• On Tutte polynomials and cycles of plane graphs
• Inapproximability of the Tutte polynomial of a planar graph
• Planar polycyclic graphs and their Tutte polynomials
• The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• Formulas for the computation of the Tutte polynomial of graphs with parallel classes
• Parity, Eulerian subgraphs and the Tutte polynomial
• On the computational complexity of the Jones and Tutte polynomials
• Computing the Tutte Polynomial on Graphs of Bounded Clique‐Width

Cites work

• Acyclic and totally cyclic orientations of combinatorial geometries
• scientific article; zbMATH DE number 3739583 (Why is no real title available?)
• On the computational complexity of the Jones and Tutte polynomials
• On the evaluation at (3,3) of the Tutte polynomial of a graph
• On the evaluation at \((j,j^2)\) of the Tutte polynomial of a ternary matroid
• On the Principal Edge Tripartition of a Graph
• On Tutte polynomials of matroids representable over GF(q)
• The Tutte polynomial of a morphism of matroids. I: Set-pointed matroids and matroid perspectives
• The Tutte polynomial of a morphism of matroids. III: Vectorial matroids
• The Tutte polynomial of a morphism of matroids. IV: Computational complexity

Cited in

(1)

• Fractionally log-concave and sector-stable polynomials: counting planar matchings and more

This page was built for publication: A parity result of Fraysseix, computational complexity of Tutte polynomials, and a conjecture on planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300994)