Counting on rainbow \(k\)-connections

DOI10.1007/978-981-97-2340-9_23MaRDI QIDQ6636091

Robert D. Barish, Tetsuo Shibuya

Publication date: 12 November 2024

zbMATH Keywords

fixed-parameter tractabilityedge colorings\#PFPTapproximation hardnessNPproper connected coloringsrainbow connected coloringstreewidth FPT

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Fundamentals of parameterized complexity
• Proper connection of graphs
• Hardness and algorithms for rainbow connection
• The monadic second-order logic of graphs. XII: Planar graphs and planar maps
• On the complexity of rainbow coloring problems
• The relative complexity of approximate counting problems
• Predecessor existence problems for finite discrete dynamical systems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Graph Theory
• On proper-path colorings in graphs
• Rainbow connectivity: hardness and tractability
• The rainbow connectivity of a graph
• Easy problems for tree-decomposable graphs
• Rainbow connection in graphs
• Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
• On Unapproximable Versions of $NP$-Complete Problems
• On the (di)graphs with (directed) proper connection number two
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

This page was built for publication: Counting on rainbow \(k\)-connections

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