Counting on rainbow k-connections

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

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

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

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)