Generalised Mycielski graphs, signature systems, and bounds on chromatic numbers
Autor: | Gord Simons, Claude Tardif, David L. Wehlau |
---|---|
Rok vydání: | 2017 |
Předmět: |
Discrete mathematics
010102 general mathematics 0102 computer and information sciences System of linear equations 01 natural sciences Graph Theoretical Computer Science Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics Linear algebra Triangle-free graph Discrete Mathematics and Combinatorics Homomorphism Chromatic scale 0101 mathematics Time complexity Mathematics |
Zdroj: | Journal of Combinatorial Theory, Series B. 122:776-793 |
ISSN: | 0095-8956 |
Popis: | We prove that the coindex of the box complex B(H) of a graph H can be measured by the generalised Mycielski graphs which admit a homomorphism to H. 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 coind(B(H))+2≤3; if the system has solutions, then χ(H)≥4. We generalise the method to other bounds on chromatic numbers using linear algebra. |
Databáze: | OpenAIRE |
Externí odkaz: |