Complexity of fall coloring for restricted graph classes
DOI10.1007/s00224-020-09982-9OpenAlexW2944675903MaRDI QIDQ5918283
Christodoulos Mitillos, Juho Lauri
Publication date: 11 June 2021
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1905.04695
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Kernel bounds for disjoint cycles and disjoint paths
- Fall colouring of bipartite graphs and Cartesian products of graphs
- On problems without polynomial kernels
- Remarks about disjoint dominating sets
- Some simplified NP-complete graph problems
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Algorithmic graph theory and perfect graphs
- Independent domination in graphs: A survey and recent results
- On graph fall-coloring: existence and constructions
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- New upper bounds on the decomposability of planar graphs
- Set Partitioning via Inclusion-Exclusion
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- NP completeness of finding the chromatic index of regular graphs
- OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
- Parameterized Algorithms
- On uniquely colorable planar graphs
This page was built for publication: Complexity of fall coloring for restricted graph classes
