𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the minimal reducible bound for outerplanar and planar graphs

✍ Scribed by Peter Mihók

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
223 KB
Volume
150
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let L be the set of all additive and hereditary properties of graphs. For P1, P2 E L we define the reducible property R = P1P2 as follows: G E PtP2 if there is a bipartition (V~,/1"2) of V(G) such that (V~) E Pi and (V2) E P2. For a property P E L, a reducible property R is called a minimal reducible bound for P if P C_ R and for each reducible property R ', R ' C R ~ P ~ R'. It is proved that the class of all outerplanar graphs has exactly two minimal reducible bounds in L. Some related problems for planar graphs are discussed.

📜 SIMILAR VOLUMES

On the delta-wye reduction for planar gr
On the delta-wye reduction for planar graphs
✍ K. Truemper 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 367 KB

We provide an elementary proof of an important theorem by G. V. Epifanov, according to which every two-terminal planar graph satisfying certain connectivity restrictions can by some sequence of series/parallel reductions and delta-wye exchanges be reduced to the graph consisting of the two terminals

On Dense Bipartite Graphs of Girth Eight
On Dense Bipartite Graphs of Girth Eight and Upper Bounds for Certain Configurations in Planar Point–Line Systems
✍ D de Caen; L.A Székely 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 956 KB

In earlier work we showed that if G(m, n) is a bipartite graph with no 4-cycles or 6-cycles, and if m<c 1 n 2 and n<c 2 m 2 , then the number of edges e is O((mn) 2Â3 ). Here we give a more streamlined proof, obtaining some sharp results; for example, if G has minimum degree at least two then e 3 -

On the max-cut problem for a planar, cub
On the max-cut problem for a planar, cubic, triangle-free graph, and the Chinese postman problem for a planar triangulation
✍ Carsten Thomassen 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

## Abstract Every 3‐connected planar, cubic, triangle‐free graph with __n__ vertices has a bipartite subgraph with at least 29__n__/24 − 7/6 edges. The constant 29/24 improves the previously best known constant 6/5 which was considered best possible because of the graph of the dodecahedron. Example