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

DOI10.1016/J.JCTB.2016.09.007zbMATH Open1350.05041arXiv1601.04642OpenAlexW2526183036MaRDI QIDQ345126FDOQ345126

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)

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.

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

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

zbMATH Keywords

homomorphismsbox complexesgeneralised Mycielski graphsgraph colourings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• The Magma algebra system. I: The user language
• Title not available (Why is that?)
• 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
• 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
• The chromatic number of the product of two 4-chromatic graphs is 4
• Topology of Hom complexes and test graphs for bounding chromatic number
• Topological lower bounds for the chromatic number: a hierarchy
• Fractional chromatic numbers of cones over graphs
• Title not available (Why is that?)
• On the Simple ℤ₂-homotopy Types of Graph Complexes and Their Simple ℤ₂-universality
• Title not available (Why is that?)

Cited In (2)

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

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)