wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

finite_regular_colorability_automatic_graphs (384B)

      1 # Finite regular colorability automatic graphs
      2 
      3 Given an [automatic_presentation] of an [automatic_graph] G, does there exist a finite number k of [regular_languages] L_1, ..., L_k that partition Sigma^* such that they form a [k_coloring] of G?
      4 
      5 When we fix k to any constant, this problem is [undecidable], cf [morvan2025homomorphism]
      6 
      7 Up: [computational_problem], [automatic_graph]