Generalized coloring of permutations
From MaRDI portal
Publication:6582372
DOI10.1007/s00453-024-01220-9MaRDI QIDQ6582372
Michal Opler, Vít Jelínek, Pavel Valtr
Publication date: 2 August 2024
Published in: Algorithmica (Search for Journal in Brave)
Algorithms in computer science (68Wxx) Permutations, words, matrices (05A05) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (05Cxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pattern matching for permutations
- Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
- Splittings and Ramsey properties of permutation classes
- Forbidden subsequences
- The existence of uniquely \(-G\) colourable graphs
- Permutations which are the union of an increasing and a decreasing subsequence
- Computational aspects of greedy partitioning of graphs
- Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
- Partitioning permutations into increasing and decreasing subsequences
- The complexity of generalized graph colorings
- Polar permutation graphs are polynomial-time recognisable
- On the growth of merges and staircases of permutation classes
- A structural characterisation of \(\mathrm{Av}(1324)\) and new bounds on its growth rate
- A new record for \(1324\)-avoiding permutations
- Rationality for subclasses of 321-avoiding permutations
- A combinatorial problem in geometry.
- Unsplittable classes of separable permutations
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- An Erd\H{o}s--Hajnal analogue for permutation classes
- Permutation classes
- A New Upper Bound for 1324-Avoiding Permutations
- On Complexity of the Subpattern Problem
- Splittability and 1-amalgamability of permutation classes
- Hardness of Permutation Pattern Matching
- Communication Complexity
- Growth rates of permutation classes: from countable to uncountable
- Generalized Coloring of Permutations
- Finding small patterns in permutations in linear time
- The complexity of satisfiability problems
- On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
This page was built for publication: Generalized coloring of permutations
