𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9

✍ Scribed by B. Mohar; R. Škrekovski; H.-J. Voss

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
326 KB
Volume
44
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph H is light in a given class of graphs if there is a constant w such that every graph of the class which has a subgraph isomorphic to H also has a subgraph isomorphic to H whose sum of degrees in G is ≤ w. Let $\cal G$ be the class of simple planar graphs of minimum degree ≥ 4 in which no two vertices of degree 4 are adjacent. We denote the minimum such w by w(H). It is proved that the cycle C~s~ is light if and only if 3 ≤ s ≤ 6, where w(C~3~) = 21 and w(C~4~) ≤ 35. The 4‐cycle with one diagonal is not light in $\cal G$, but it is light in the subclass ${\cal G}^T$ consisting of all triangulations. The star K~1,s~ is light if and only if s ≤ 4. In particular, w(K~1,3~) = 23. The paths P~s~ are light for 1 ≤ s ≤ 6, and heavy for s ≥ 8. Moreover, w(P~3~) = 17 and w(P~4~) = 23. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 261–295, 2003

📜 SIMILAR VOLUMES

On Light Edges and Triangles in Planar G
On Light Edges and Triangles in Planar Graphs of Minimum Degree Five
✍ Oleg V. Borodin; Daniel P. Sanders 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 342 KB 👁 1 views

## Abstract This paper presents two tight inequalities for planar graphs of minimum degree five. An edge or face of a plane graph is light if the sum of the degrees of the vertices incident with it is small. A light edge inequality is presented which shows that planar graphs of minimum degree five

Connected subgraphs with small degree su
Connected subgraphs with small degree sums in 3-connected planar graphs
✍ Enomoto, Hikoe; Ota, Katsuhiro 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It is well-known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3-connected planar graph has an edge xy such that deg(x) + deg(y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we sh

Graphs of degree 4 are 5-edge-choosable
Graphs of degree 4 are 5-edge-choosable
✍ Juvan, Martin; Mohar, Bojan; ??krekovski, Riste 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 312 KB 👁 1 views

It is shown that every simple graph with maximal degree 4 is 5-edgechoosable.

Edge disjoint Hamilton cycles in sparse
Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk
✍ Bollob�s, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 3 views

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for

Acyclic edge coloring of graphs with max
Acyclic edge coloring of graphs with maximum degree 4
✍ Manu Basavaraju; L. Sunil Chandran 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

## Abstract An __acyclic__ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The __acyclic chromatic index__ of a graph is the minimum number __k__ such that there is an acyclic edge coloring using __k__ colors and is denoted by __a__′(__G__). It was conj

On total 9-coloring planar graphs of max
On total 9-coloring planar graphs of maximum degree seven
✍ Sanders, Daniel P.; Zhao, Yue 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 3 views

Given a graph G, a total k-coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If ∆(G) is the maximum degree of G, then no graph has a total ∆-coloring, but Vizing conjectured that every graph has a total (∆ + 2)-coloring. This Total Coloring Conjecture rem