Grassmann homomorphism and Hajós-type theorems

DOI10.1016/j.laa.2017.02.013zbMath1406.05031OpenAlexW2588363153MaRDI QIDQ518115

Tommy R. Jensen

Publication date: 28 March 2017

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2017.02.013

zbMATH Keywords

combinatoricshomomorphismcomplexity classesfinite GrassmannianHajós construction

Mathematics Subject Classification ID

Grassmannians, Schubert varieties, flag manifolds (14M15) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Hajós-Type Constructions and Neighborhood Complexes, Hajós and Ore constructions for digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A constructive approach to the critical problem for matroids
• On 4-critical planar graphs with high edge density
• An analogue of Hajós' theorem for the circular chromatic number. II
• Hajós' theorem for list coloring
• A Hajós-like theorem for list coloring
• The complexity of the Hajós calculus for planar graphs
• An analogue of Hajós’ Theorem for the circular chromatic number
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• Some Colouring Problems and their Complexity
• The Homomorphism Structure of Classes of Graphs
• [https://portal.mardi4nfdi.de/wiki/Publication:4256105 Haj�s constructions of critical graphs]
• The Complexity of the Hajós Calculus
• Reducibility among Combinatorial Problems
• Using Hajós’ Construction to Generate Hard Graph 3-Colorability Instances
• A Contribution to the Theory of Chromatic Polynomials