Generalized coloring of permutations

DOI10.1007/S00453-024-01220-9MaRDI QIDQ6582372FDOQ6582372

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

Publication date: 2 August 2024

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

recognitiontree automatapermutation class

Mathematics Subject Classification ID

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

Cites Work

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

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)