scientific article; zbMATH DE number 7829468

MaRDI QIDQ6126505

Robert D. Barish

Publication date: 9 April 2024

Full work available at URL: https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1556

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

edge coloringconnectivityTutte polynomialvertex coloringstrong connectivityFPRAS\#Punilateral\#P-completeproper connected coloringcounting hardness

Mathematics Subject Classification ID

Graph polynomials (05C31) Enumeration in graph theory (05C30) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Cites Work

• Note on vertex and total proper connection numbers
• Proper connection of graphs
• The complexity of computing the permanent
• Inapproximability of the Tutte polynomial
• Convexity in oriented matroids
• Alternating cycles and paths in edge-coloured multigraphs: A survey
• The relative complexity of approximate counting problems
• The rainbow connectivity of a graph
• A Dichotomy Theorem for Polynomial Evaluation
• Rainbow connection in graphs
• The Complexity of Enumeration and Reliability Problems
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• Properly Colored Connectivity of Graphs
• On the computational complexity of the Jones and Tutte polynomials
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• The Computational Complexity of Tutte Invariants for Planar Graphs
• Max flows in O(nm) time, or better
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• On the (di)graphs with (directed) proper connection number two
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item