Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1002/jgt.22092 | Journal of Graph Theory |
Keywords | Field | DocType |
graph,direct product,homomorphism (of graphs),homomorphic image,uniquely n-colorable,Ht-construct,P-string,HPEs-construct | Graph theory,Discrete mathematics,Graph,Combinatorics,Direct product,Graph power,Vertex (geometry),Chromatic scale,Conjecture,Mathematics,Special case | Journal |
Volume | Issue | ISSN |
85 | 2 | 0364-9024 |
Citations | PageRank | References |
1 | 0.36 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Izak Broere | 1 | 143 | 31.30 |
| Moroli D. V. Matsoha | 2 | 1 | 0.70 |