Generalised Mycielski graphs, signature systems, and bounds on chromatic numbers

DOI10.1016/J.JCTB.2016.09.007MaRDI QIDQ345126zbMATH OpenOpenAlexFDO

Authors Gord Simons, Claude Tardif, David Wehlau

Publication date 25 November 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.04642

zbMATH Keywords

homomorphismsbox complexesgeneralised Mycielski graphsgraph colourings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We prove that the coindex of the box complex $mathrmB(H)$ of a graph $H$ can be measured by the generalised Mycielski graphs which admit a homomorphism to it. As a consequence, we exhibit for every graph $H$ a system of linear equations solvable in polynomial time, with the following properties: If the system has no solutions, then $mathrmcoind(mathrmB(H))+2leq3$; if the system has solutions, then $chi(H)geq4$. We generalise the method to other bounds on chromatic numbers using linear algebra.

Recommendations

• Circular chromatic number and a generalization of the construction of Mycielski.
• Generalised Mycielski graphs and the Borsuk-Ulam theorem
• Topological lower bounds for the chromatic number: a hierarchy
• scientific article; zbMATH DE number 5704224
• A lower bound on the chromatic number of Mycielski graphs

Cites work

• scientific article; zbMATH DE number 5704224 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 3245178 (Why is no real title available?)
• Fractional chromatic numbers of cones over graphs
• Kneser's conjecture, chromatic number, and homotopy
• Local chromatic number and distinguishing the strength of topological obstructions
• Local chromatic number, Ky Fan's theorem, and circular colorings
• On the Simple ℤ₂-homotopy Types of Graph Complexes and Their Simple ℤ₂-universality
• The Magma algebra system. I: The user language
• The chromatic number of the product of two 4-chromatic graphs is 4
• Topological lower bounds for the chromatic number: a hierarchy
• Topology of Hom complexes and test graphs for bounding chromatic number
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler

Cited in

(2)

• A generalization of Gale's lemma
• Graph classes generated by Mycielskians

Describes a project that uses

Uses Software

• Magma

This page was built for publication: Generalised Mycielski graphs, signature systems, and bounds on chromatic numbers

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