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: |
|
Full Text from ScienceDirect