Large independent sets in subquartic planar graphs

DOI10.1007/978-3-319-30139-6_17zbMATH Open1475.68140OpenAlexW2345383505MaRDI QIDQ2803824FDOQ2803824

Authors: 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

Recommendations

• Large independent sets in triangle-free planar graphs
• Large independent sets in triangle-free planar graphs
• Bounded-degree independent sets in planar graphs
• Planar graphs have independence ratio at least 3/13
• scientific article; zbMATH DE number 1979518

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Parameterizing above or below guaranteed values
• Betweenness parameterized above tight lower bound
• Max-Cut parameterized above the Edwards-Erdős bound
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parameterized algorithms
• Title not available (Why is that?)
• The four-colour theorem
• Every planar map is four colorable
• Graph colouring and the probabilistic method
• On the existence of subexponential parameterized algorithms
• Independent sets in triangle-free cubic planar graphs
• Maximum independent sets in 3- and 4-regular Hamiltonian graphs
• Approximate tree decompositions of planar graphs in linear time
• Large independent sets in triangle-free planar graphs
• Local tree-width, excluded minors, and approximation algorithms
• Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Title not available (Why is that?)
• A fractional analogue of Brooks' theorem
• Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
• Bisections above Tight Lower Bounds
• Odd Cycle Transversals and Independent Sets in Fullerene Graphs
• The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\)
• New lower bound on Max Cut of hypergraphs with an application to \(r\)-Set Splitting
• Subcubic triangle-free graphs have fractional chromatic number at most \(14/5\)

Cited In (4)

• Finding detours is fixed-parameter tractable
• Title not available (Why is that?)
• Large independent sets in triangle-free planar graphs
• Large independent sets in regular graphs of large girth

This page was built for publication: Large independent sets in subquartic planar graphs

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