Maximum 4-degenerate subgraph of a planar graph

MaRDI QIDQ490312zbMATH OpenFDO

Authors R. Lukot'ka, J. Mazák, Xuding Zhu

Publication date 22 January 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.6195, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p11

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

degenerate subgraphslist colouringplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: A graph $G$ is $k$-degenerate if it can be transformed into an empty graph by subsequent removals of vertices of degree $k$ or less. We prove that every connected planar graph with average degree $dge2$ has a 4-degenerate induced subgraph containing at least $(38-d)/36$ of its vertices. This shows that every planar graph of order $n$ has a 4-degenerate induced subgraph of order more than $8/9cdotn$. We also consider a local variation of this problem and show that in every planar graph with at least 7 vertices, deleting a suitable vertex allows us to subsequently remove at least 6 more vertices of degree four or less.

Review text

Summary: A graph \(G\) is \(k\)-degenerate if it can be transformed into an empty graph by subsequent removals of vertices of degree \(k\) or less. We prove that every connected planar graph with average degree \(d \geq 2\) has a 4-degenerate induced subgraph containing at least \( (38 - d)/36\) of its vertices. This shows that every planar graph of order \(n\) has a 4-degenerate induced subgraph of order more than \(8/9 \cdot n\). We also consider a local variation of this problem and show that in every planar graph with at least 7 vertices, deleting a suitable vertex allows us to subsequently remove at least 6 more vertices of degree four or less.

Recommendations

• Degenerated induced subgraphs of planar graphs
• 3‐Degenerate induced subgraph of a planar graph
• Large induced degenerate subgraphs
• Induced 2-degenerate subgraphs of triangle-free planar graphs
• Decomposing a planar graph into degenerate graphs

Cites work

• k-Degenerate Graphs
• Disproof of the list Hadwiger conjecture
• Every planar graph is 5-choosable
• scientific article; zbMATH DE number 3565019 (Why is no real title available?)
• scientific article; zbMATH DE number 1882351 (Why is no real title available?)
• Large induced degenerate subgraphs

Cited in

(9)

• Induced 2-degenerate subgraphs of triangle-free planar graphs
• A better bound on the largest induced forests in triangle-free planar graph
• Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph
• Planar graphs without specific cycles are 2-degenerate
• Planarization and fragmentability of some classes of graphs
• The maximum number of paths of length four in a planar graph
• Degenerated induced subgraphs of planar graphs
• 3‐Degenerate induced subgraph of a planar graph
• A note on large degenerate induced subgraphs in sparse graphs

This page was built for publication: Maximum 4-degenerate subgraph of a planar graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490312)