Maximum locally irregular induced subgraphs via minimum irregulators

DOI10.1016/J.DAM.2024.12.007MaRDI QIDQ6671395zbMATH OpenFDO

Authors Foivos Fioravantes, Nikolaos Melissinos, Theofilos Triommatis

Publication date 27 January 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2024.12.007

zbMATH Keywords

approximabilityFPTlargest induced subgraphlocally irregulartreewidthW-hardness

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the complexity of determining the irregular chromatic index of a graph
• On decomposing graphs of large minimum degree into locally irregular subgraphs
• On decomposing regular graphs into locally irregular subgraphs
• On locally irregular decompositions of subcubic graphs
• Decomposing degenerate graphs into locally irregular subgraphs

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• A solution to the 1-2-3 conjecture
• Bounding the distant irregularity strength of graphs via a non-uniformly biased random weight assignment
• Complexity of approximating bounded variants of optimization problems
• Complexity of finding maximum locally irregular induced subgraphs
• Complexity of finding maximum regular induced subgraphs with prescribed degree
• Decomposing graphs into a constant number of locally irregular subgraphs
• Decomposing split graphs into locally irregular graphs
• Edge weights and vertex colours
• Face covers and the genus problem for apex graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fundamentals of parameterized complexity
• Highly irregular graphs
• How to Define an Irregular Graph
• scientific article; zbMATH DE number 4095506 (Why is no real title available?)
• scientific article; zbMATH DE number 4097437 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Irregularity in graphs
• Irregularity strength of regular graphs
• Lower bounds based on the exponential time hypothesis
• On decomposing graphs of large minimum degree into locally irregular subgraphs
• On decomposing regular graphs into locally irregular subgraphs
• On graph irregularity strength
• On the complexity of finding large odd induced subgraphs and odd colorings
• On the computational hardness based on linear fpt-reductions
• Parameterized algorithms
• Parameterized complexity of finding regular induced subgraphs
• Parameterized complexity of finding subgraphs with hereditary properties.
• Strong computational lower bounds via parameterized complexity
• The k-regular induced subgraph problem
• The node-deletion problem for hereditary properties is NP-complete
• Tight lower bounds for certain parameterized NP-hard problems

Cited in

(1)

• Parameterised distance to local irregularity

This page was built for publication: Maximum locally irregular induced subgraphs via minimum irregulators

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