Premium
Applications of Hajós‐Type Constructions to the Hedetniemi Conjecture
Author(s) -
Broere Izak,
Matsoha Moroli D. V.
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22092
Subject(s) - combinatorics , mathematics , clique number , conjecture , vertex (graph theory) , graph , discrete mathematics , clique graph , graph power , line graph
Hedetniemi conjectured in 1966 that if G and H are finite graphs with chromatic number n , then the chromatic number χ ( G × H ) of the direct product of G and H is also n . We mention two well‐known results pertaining to this conjecture and offer an improvement of the one, which partially proves the other. The first of these two results is due to Burr et al. (Ars Combin 1 (1976), 167–190), who showed that when every vertex of a graph G with χ ( G ) = n + 1 is contained in an n ‐clique, then χ ( G × H ) = n + 1 whenever χ ( H ) = n + 1 . The second, by Duffus et al. (J Graph Theory 9 (1985), 487–495), and, obtained independently by Welzl (J Combin Theory Ser B 37 (1984), 235–244), states that the same is true when G and H are connected graphs each with clique number n . Our main result reads as follows: If G is a graph with χ ( G ) = n + 1 and has the property that the subgraph of G induced by those vertices of G that are not contained in an n ‐clique is homomorphic to an ( n + 1 ) ‐critical graph H , then χ ( G × H ) = n + 1 . This result is an improvement of the result by the first authors. In addition we will show that our main result implies a special case of the result by the second set of authors. Our approach will employ a construction of a graph F , with chromatic number n + 1 , that is homomorphic to G and H .