Line-Polar Graphs: Characterization and Recognition

DOI10.1137/100789208MaRDI QIDQ3225119zbMATH OpenOpenAlexFDO

Authors Ross Churchley, Jing Huang

Publication date 15 March 2012

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/100789208

zbMATH Keywords

structural characterizationmonopolar partitionline-polar graphlinear time recognition algorithmline-monopolar graphpolar partition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• Polyhedral characterizations and perfection of line graphs
• Recognizing polar planar graphs using new results for monopolarity
• Recognizing line-polar bipartite graphs in time \(O(n)\)
• A characterization of half-dual polar graphs
• Complexity and algorithms for recognizing polar and monopolar graphs
• A new characterization of the dual polar graphs
• scientific article; zbMATH DE number 3966134
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• Linear recognition of almost interval graphs
• scientific article; zbMATH DE number 3906540

Cited in

(13)

• The recognition problem for line bigraphs
• Algorithms for unipolar and generalized split graphs
• A forbidden subgraph characterization of line-polar bipartite graphs
• Solving partition problems with colour-bipartitions
• On finite characterizability of graphs with restricted equivalence partition number in classes of polar graphs
• Minimal obstructions to \(( \infty , k )\)-polarity in cographs
• On the Polarity and Monopolarity of Graphs
• Monopolar graphs: complexity of computing classical graph parameters
• List monopolar partitions of claw-free graphs
• Recognizing line-polar bipartite graphs in time \(O(n)\)
• Polar cographs
• Recognizing generalized transmission graphs of line segments and circular sectors
• Complexity and algorithms for recognizing polar and monopolar graphs

This page was built for publication: Line-Polar Graphs: Characterization and Recognition

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