Large Induced Acyclic and Outerplanar Subgraphs of 2-Outerplanar Graph

Borradaile, Glencora; Le, Hung; Sherman-Bennett, Melissa
November 2017
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1621
Academic Journal
Albertson and Berman conjectured that every planar graph has an induced forest on half of its vertices. The best known lower bound, due to Borodin, is that every planar graph has an induced forest on two fifths of its vertices. In a related result, Chartran and Kronk, proved that the vertices of every planar graph can be partitioned into three sets, each of which induce a forest. We show tighter results for 2-outerplanar graphs. We show that every 2-outerplanar graph has an induced forest on at least half the vertices by showing that its vertices can be partitioned into two sets, each of which induces a forest. We also show that every 2-outerplanar graph has an induced outerplanar graph on at least two-thirds of its vertices.


Related Articles

  • PLANARITY OF ECCENTRIC DIGRAPH OF GRAPHS. HUILGOL, MEDHA ITAGI; ULLA S., SYED ASIF // Journal of Combinatorics & System Sciences;2014, Vol. 39 Issue 1/4, p33 

    The eccentricity e(u) of a vertex u is the maximum distance of u to any other vertex of G. A vertex v is an eccentric vertex of vertex u if the distance from u to v is equal to e(u). The eccentric digraph ED(G) of a graph(digraph) G is the digraph that has the same vertex set as G and an arc...

  • List edge and list total coloring of 1-planar graphs. Zhang, Xin; Wu, Jianliang; Liu, Guizhen // Frontiers of Mathematics in China;Oct2012, Vol. 7 Issue 5, p1005 

    A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree Δ is (Δ+1)-edge-choosable and (Δ+2)-total-choosable if Δ ⩾ 16, and is Δ-edge-choosable and...

  • Criticality of Counterexamples to Toroidal Edge-Hamiltonicity. Ellingham, M.; Marshall, Emily // Graphs & Combinatorics;Jan2016, Vol. 32 Issue 1, p111 

    A well-known conjecture of Grünbaum and Nash-Williams proposes that $$4$$ -connected toroidal graphs are Hamiltonian. The corresponding results for $$4$$ -connected planar and projective-planar graphs were proved by Tutte and by Thomas and Yu, respectively, using induction arguments that...

  • Bipartite and Planar Power Graphs of Finite Groups. Maity, S. K. // Southeast Asian Bulletin of Mathematics;2015, Vol. 39 Issue 4, p539 

    The undirected power graph G(S) of a semigroup S is an undirected graph whose vertex set is S and two vertices a, b ∈ S are adjacent if and only if a ≠ b and am = b or bm = a for some positive integer m. In this paper we characterize the class of finite groups S for which G(S) is...

  • Light Graphs In Planar Graphs Of Large Girth. Hudák, Peter; Maceková, Mária; Madaras, Tomáš; Široczki, Pavol // Discussiones Mathematicae: Graph Theory;Feb2016, Vol. 36 Issue 1, p227 

    A graph H is defined to be light in a graph family 풢 if there exist finite numbers φ( H, 풢) and w( H, 풢) such that each G ∈ 풢 which contains H as a subgraph, also contains its isomorphic copy K with Δ G( K) ≤ φ( H, 풢) and ∑ x∈V(K)...

  • Unique-Maximum Coloring Of Plane Graphs. Fabrici, Igor; Göring, Frank // Discussiones Mathematicae: Graph Theory;Feb2016, Vol. 36 Issue 1, p95 

    A unique-maximum k-coloring with respect to faces of a plane graph G is a coloring with colors 1, . . . , k so that, for each face of G, the maximum color occurs exactly once on the vertices of α. We prove that any plane graph is unique-maximum 3-colorable and has a proper unique-maximum...

  • Split Euler Tours In 4-Regular Planar Graphs. Couch, PJ; Daniel, B.D.; Guidry, R.; Paul Wright, W. // Discussiones Mathematicae: Graph Theory;Feb2016, Vol. 36 Issue 1, p23 

    The construction of a homing tour is known to be NP-complete. On the other hand, the Euler formula puts su cient restrictions on plane graphs that one should be able to assert the existence of such tours in some cases; in particular we focus on split Euler tours (SETs) in 3-connected, 4-regular,...

  • Planar and Quasi-Planar Simultaneous Geometric Embedding. DI GIACOMO, EMILIO; DIDIMO, WALTER; LIOTTA, GIUSEPPE; MEIJER, HENK; WISMATH, STEPHEN K. // Computer Journal;Nov2015, Vol. 58 Issue 11, p3126 

    A simultaneous geometric embedding (SGE) of two planar graphs G1 and G2 with the same vertex set is a pair of straight-line planar drawings Γ1 of G1 and Γ2 of G2 such that each vertex is drawn at the same point in Γ1 Γ2. Many papers have been devoted to the study of which pairs...


    The annihilator graph AG(R) of a commutative ring R is a simple undirected graph with the vertex set Z(R)* and two distinct vertices are adjacent if and only if ann(x) U ann(y) ≠ ann(xy). In this paper we give the sufficient condition for a graph AG(R) to be complete. We characterize rings...

  • Vertex Equitable Labeling of Cycle and Star Related Graphs. Jeyanthi, P.; Maheswari, A.; Vijayalaksmi, M. // Journal of Scientific Research;2015, Vol. 7 Issue 3, p33 

    Let G be a graph with p vertices and q edges and A = 0,1,2,..., A vertex labeling f: V (G) -> A induces an edge labeling f* defined by f*(uv) = f(u) + f(v) for all edges uv. For a∈ A, let vf (a) be the number of vertices v with f(v) = a. A graph G is said to be vertex equitable if there...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics