The matching extendability of optimal 1-planar graphs

DOI10.1007/s00373-018-1932-6zbMath1402.05045OpenAlexW2887184711WikidataQ129380118 ScholiaQ129380118MaRDI QIDQ1756050

Jun Fujisawa, Yusuke Suzuki, Keita Segawa

Publication date: 11 January 2019

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-018-1932-6

zbMATH Keywords

extendabilityperfect matchingoptimal 1-planar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (6)

On the edge-connectivity and restricted edge-connectivity of optimal 1-planar graphs ⋮ The maximum matching extendability and factor-criticality of 1-planar graphs ⋮ Optimal 1-planar multigraphs ⋮ Unnamed Item ⋮ 1-Planar Graphs ⋮ The distance matching extension in \(K_{1,k}\)-free graphs with high local connectedness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Outer 1-planar graphs
• On drawings and decompositions of 1-planar graphs
• The 2-extendability of 5-connected graphs on surfaces with large representativity
• Extending matchings in planar graphs. IV
• A linear-time algorithm for 7-coloring 1-plane graphs
• The structure of 1-planar graphs
• Relationship among triangulations, quadrangulations and optimal 1-planar graphs
• 4-connected projective planar graphs are Hamiltonian
• Ein Sechsfarbenproblem auf der Kugel
• On the matching extendability of graphs in surfaces
• Proximity thresholds for matching extension in planar and projective planar triangulations
• Re-embeddings of Maximum 1-Planar Graphs
• Recent Progress in Matching Extension
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing

This page was built for publication: The matching extendability of optimal 1-planar graphs