Discontinuities in the complexities of some graph recognition problems

MaRDI QIDQ2848780zbMATH OpenFDO

Authors Augustine Moshi

Publication date 26 September 2013

Published in South Pacific Journal of Pure and Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

matching cutset

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

The author introduces the notion of a complexity jump. However, only one result is shown which states that every connected graph of order at least 8 with maximum degree 3 has a matching cutset. This result has already appeared in the author's earlier paper [J. Graph Theory 13, No. 5, 527--536 (1989; Zbl 0725.05055)].

Recommendations

• Matching cutsets in graphs
• scientific article; zbMATH DE number 2044946
• The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract)
• A note on the jump graph of a graph
• scientific article; zbMATH DE number 19225

Cited in

(5)

• Graph approach to solving problems of combinatorial recognition
• Recognizing brittle graphs: Remarks on a paper of Hoàng and Khouzam
• Об одной задаче распознавания предфрактального графа
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• Recognizing tough graphs is NP-hard

This page was built for publication: Discontinuities in the complexities of some graph recognition problems

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