Large Independent Sets in Subquartic Planar Graphs
From MaRDI portal
Publication:2803824
DOI10.1007/978-3-319-30139-6_17zbMath1475.68140OpenAlexW2345383505MaRDI QIDQ2803824
Publication date: 3 May 2016
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-30139-6_17
Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximate tree decompositions of planar graphs in linear time
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Maximum independent sets in 3- and 4-regular Hamiltonian graphs
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
- Parameterizing above or below guaranteed values
- The four-colour theorem
- The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\)
- On the existence of subexponential parameterized algorithms
- Betweenness parameterized above tight lower bound
- Independent sets in triangle-free cubic planar graphs
- Local tree-width, excluded minors, and approximation algorithms
- Max-Cut Parameterized above the Edwards-Erdős Bound
- 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
- Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average
- Large Independent Sets in Triangle-Free Planar Graphs
- Every planar map is four colorable
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Odd Cycle Transversals and Independent Sets in Fullerene Graphs
- Bisections above Tight Lower Bounds
- Subcubic triangle-free graphs have fractional chromatic number at most 14/5
- Parameterized Algorithms
- Graph colouring and the probabilistic method
