Large Independent Sets in Subquartic Planar Graphs

DOI10.1007/978-3-319-30139-6_17zbMath1475.68140OpenAlexW2345383505MaRDI QIDQ2803824

Matthias Mnich

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

Mathematics Subject Classification ID

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

Large Independent Sets in Triangle-Free Planar Graphs, Finding Detours is Fixed-Parameter Tractable

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