Large independent sets in subquartic planar graphs

DOI10.1007/978-3-319-30139-6_17MaRDI QIDQ2803824zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(4)

• Finding detours is fixed-parameter tractable
• scientific article; zbMATH DE number 15666 (Why is no real title available?)
• 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)