Answers to some problems about graph coloring test graphs

DOI10.1016/J.EJC.2014.10.006MaRDI QIDQ482122zbMATHOpenAlexFDO

Authors Takahiro Matsushita

Publication date 19 December 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

homotopy test graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We prove that a graph whose chromatic number is 2 is a homotopy test graph. We also prove that there is a graph $K$ with two involutions $gamm{a}_1$ and $gamm{a}_2$ such that $(K,gamm{a}_1)$ is a Stiefel-Whitney test graph, but $(K,gamm{a}_2)$ is not. These are answers to some of the problems suggested by Kozlov.

Recommendations

• Homology tests for graph colorings
• The equivariant topology of stable Kneser graphs
• Paths of homomorphisms from stable Kneser graphs
• The equivariant topology of stable Kneser graphs
• A topological lower bound for the chromatic number of a special family of graphs

Cites work

• A counterexample to a conjecture of Björner and Lovász on the \(\chi\)-coloring complex
• A short proof of \(w_{1}^n (\text{Hom}(C_{2r+1}, K_{n+2})) = 0\) for all \(n\) and a graph colouring theorem by Babson and Kozlov
• Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
• Cobounding odd cycle colorings
• Combinatorial algebraic topology
• Complexes of graph homomorphisms
• Graph colorings, spaces of edges and spaces of circuits
• Kneser's conjecture, chromatic number, and homotopy
• Proof of the Lovász conjecture
• Topology of Hom complexes and test graphs for bounding chromatic number

Cited in

(4)

• Connectedness of certain graph coloring complexes
• Homology tests for graph colorings
• Neighborhood complexes, homotopy test graphs and an application to coloring of product graphs
• Homotopy types of the Hom complexes of graphs

This page was built for publication: Answers to some problems about graph coloring test graphs

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