Large Independent Sets in Triangle-Free Planar Graphs
From MaRDI portal
Publication:5270410
DOI10.1137/16M1061862zbMath1371.68111OpenAlexW2963759319MaRDI QIDQ5270410
Publication date: 23 June 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1061862
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Induced 2-degenerate subgraphs of triangle-free planar graphs, Linear kernels and linear-time algorithms for finding large cuts, Fractional Coloring of Planar Graphs of Girth Five, Finding Detours is Fixed-Parameter Tractable, Above guarantee parameterization for vertex cover on graphs with maximum degree 4
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Sparsity. Graphs, structures, and algorithms
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Solving MAX-\(r\)-SAT above a tight lower bound
- Parameterizing above or below guaranteed values
- Planar Ramsey numbers
- Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
- Quickly excluding a planar graph
- The four-colour theorem
- Betweenness parameterized above tight lower bound
- Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Independent sets in triangle-free cubic planar graphs
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Large Independent Sets in Subquartic Planar Graphs
- On Multiway Cut Parameterized above Lower Bounds
- New Lower Bound on Max Cut of Hypergraphs with an Application to r -Set Splitting
- A Fractional Analogue of Brooks' Theorem
- Large Independent Sets in Triangle-Free Planar Graphs
- Three-coloring triangle-free planar graphs in linear time
- Planar Graphs of Odd-Girth at Least 9 are Homomorphic to the Petersen Graph
- Girth and fractional chromatic number of planar graphs
- Some Ramsey-Type Numbers and the Independence Ratio
- Every planar map is four colorable
- Coloring graphs with fixed genus and girth
- The Ramsey number R(3, t) has order of magnitude t2/log t
- First order properties on nowhere dense structures
- Faster Parameterized Algorithms Using Linear Programming
- Bisections above Tight Lower Bounds
- Testing first-order properties for subclasses of sparse graphs
