Generalized coloring of permutations

DOI10.1007/S00453-024-01220-9MaRDI QIDQ6582372zbMATH OpenFDO

Authors Vít Jelínek, Michal Opler, Pavel Valtr

Publication date 2 August 2024

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00453-024-01220-9

zbMATH Keywords

permutation classrecognitiontree automata

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Coloring of graphs and hypergraphs (05C15) Graph theory (05Cxx) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms in computer science (68Wxx)

Cites work

• P₄-colorings and P₄-bipartite graphs
• A c^k n 5-approximation algorithm for treewidth
• A combinatorial problem in geometry.
• A new record for \(1324\)-avoiding permutations
• A new upper bound for 1324-avoiding permutations
• A structural characterisation of \(\mathrm{Av}(1324)\) and new bounds on its growth rate
• An Erdős-Hajnal analogue for permutation classes
• Communication Complexity
• Computational aspects of greedy partitioning of graphs
• Finding small patterns in permutations in linear time
• Forbidden subsequences
• Generalized Coloring of Permutations
• Growth rates of permutation classes: from countable to uncountable
• Hardness of permutation pattern matching
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 2159638 (Why is no real title available?)
• scientific article; zbMATH DE number 3997796 (Why is no real title available?)
• scientific article; zbMATH DE number 3999312 (Why is no real title available?)
• scientific article; zbMATH DE number 7559423 (Why is no real title available?)
• scientific article; zbMATH DE number 7803600 (Why is no real title available?)
• On Complexity of the Subpattern Problem
• On the growth of merges and staircases of permutation classes
• On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
• Partitioning permutations into increasing and decreasing subsequences
• Pattern matching for permutations
• Permutation classes
• Permutations which are the union of an increasing and a decreasing subsequence
• Polar permutation graphs are polynomial-time recognisable
• Rationality for subclasses of 321-avoiding permutations
• Splittability and 1-amalgamability of permutation classes
• Splittings and Ramsey properties of permutation classes
• The complexity of generalized graph colorings
• The complexity of satisfiability problems
• The existence of uniquely \(-G\) colourable graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Unsplittable classes of separable permutations
• Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard

This page was built for publication: Generalized coloring of permutations

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