𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Finding short cycles in planar graphs using separators

✍ Scribed by Dana Richards

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
635 KB
Volume
7
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Planar graph colorings without short mon
Planar graph colorings without short monochromatic cycles
✍ TomΓ‘Ε‘ Kaiser; Riste Ε krekovski πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 126 KB πŸ‘ 1 views

## Abstract It is well known that every planar graph __G__ is 2‐colorable in such a way that no 3‐cycle of __G__ is monochromatic. In this paper, we prove that __G__ has a 2‐coloring such that no cycle of length 3 or 4 is monochromatic. The complete graph __K__~5~ does not admit such a coloring. On

Short cycles in mediate graphs
Short cycles in mediate graphs
✍ G. Hahn; D. Sotteau; H. Sun πŸ“‚ Article πŸ“… 1983 πŸ› Elsevier Science 🌐 English βš– 142 KB
Acyclic 5-choosability of planar graphs
Acyclic 5-choosability of planar graphs without adjacent short cycles
✍ O. V. Borodin; A. O. Ivanova πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 93 KB πŸ‘ 1 views

The conjecture on acyclic 5-choosability of planar graphs [Borodin et al., 2002] as yet has been verified only for several restricted classes of graphs. None of these classes allows 4-cycles. We prove that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cy

On certain Hamiltonian cycles in planar
On certain Hamiltonian cycles in planar graphs
✍ BοΏ½hme, T.; Harant, J.; TkοΏ½?, M. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 162 KB πŸ‘ 2 views

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that mus