zbMATH — the first resource for mathematics

Maximal outerplanar graphs with perfect face-independent vertex covers. (English) Zbl 0808.05042
Let \(G = (V, E)\) be a 2-connected planar graph, embedded in the plane. A subset \(W \subseteq V\) is called perfect face-independent vertex cover (FIVC) of \(G\) if every face of \(G\) has exactly one vertex in \(W\). The main result characterizes those maximal outerplanar graphs which admit plane embeddings with perfect FIVCs.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C05 Trees
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] M. Fellows, Personal communication, 1986.
[2] Fellows, M.; Hickling, F.; Syslo, M.M., A topological parameterization and hard graph problems, (), 69-78 · Zbl 0654.05027
[3] Syslo, M.M., Independent face and vertex covers in plane graphs, Banach center publ., 25, 177-185, (1989) · Zbl 0741.05054
[4] Syslo, M.M.; Winter, P., Independent covers in outerplanar graphs, (), 243-254 · Zbl 0656.05049
[5] Syslo, M.M.; Winter, P., In-trees and plane embeddings of outerplanar graphs, Bit, 30, 83-90, (1990) · Zbl 0692.68019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.