On the Hadwiger's conjecture for graph products
type: Item
instance of: scholarly article
title: On the Hadwiger's conjecture for graph products
zbMATH Open document ID: 1119.05041
author: L. Sunil Chandran
author: Naveen Sivadasan
published in: Discrete Mathematics
publication date: 2007-02-13T00:00:00Z
review text: The Hadwiger's conjecture for graphs is given in terms of their prime factorization. It is shown (among other things) that the Hadwiger conjecture is true for a graph \(G\) if the product dimension of \(G\) is at least \(2\log_2(\chi(G))+ 3\). The Hadwiger number of well-known graph products like \(d\)-dimensional hypercubes, Hamming graphs and the \(d\)-dimensional grids are consider, too.
reviewed by: Jozef Fiamčík
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C83
zbMATH DE Number: 5124993
zbMATH Keywords: Hadwiger's conjecture
zbMATH Keywords: Hadwiger number
zbMATH Keywords: graph minor
zbMATH Keywords: graph product
zbMATH Keywords: hypercube
MaRDI profile type: Publication
full work available at URL: j.disc.2006.06.019
OpenAlex ID: W2021312663
Wikidata QID: Q123308179
cites work: Cartesian graph factorization at logarithmic cost per edge
cites work: Q4947393
cites work: Dense minors in graphs of large girth
cites work: On rigid circuit graphs
cites work: In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
cites work: On Hadwiger's Number and the Stability Number
cites work: Cycles and paths through specified vertices in k-connected graphs
cites work: Q4860774
cites work: Q5837979
cites work: Coloring graph products---a survey
cites work: Q3333070
cites work: Lower bound of the Hadwiger number of graphs by their average degree
cites work: Q4713810
cites work: Minors in graphs of large girth
cites work: Homomorphieeigenschaften und mittlere Kantendichte von Graphen
cites work: Homomorphiesätze für Graphen
cites work: Contractions of graphs: A theorem of Ore and an extremal problem
cites work: Hamiltonian circuits in random graphs
cites work: Hadwiger's conjecture for line graphs
cites work: Clique minors in graphs and their complements
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Hadwiger's conjecture for \(K_ 6\)-free graphs
cites work: Graphs with Given Group and Given Graph-Theoretical Properties
cites work: Fractional colouring and Hadwiger's conjecture
cites work: On Hadwiger's number---A problem of the Nordhaus-Gaddum type
cites work: An extremal function for contractions of graphs
cites work: Girth in graphs
cites work: Über eine Eigenschaft der ebenen Komplexe
cites work: On some graph-theoretical problems of V. G. Vizing
DOI: 10.1016/J.DISC.2006.06.019
Recommended article: On multiplicative graphs and the product conjecture
Recommended article: Hadwiger number and the Cartesian product of graphs
Recommended article: The Farrell-Jones conjecture for graph products
Recommended article: Hedetniemi's conjecture and fiber products of graphs
Recommended article: Partial product of graphs and Vizing's conjecture
Recommended article: The Conjugacy Problem for Finite Graph Products
Recommended article: Hedetniemi's conjecture and the retracts of a product of graphs
Recommended article: Q4014306
Recommended article: Behzad-Vizing conjecture and Cartesian product graphs
Recommended article: On a Vizing-like conjecture for direct product graphs
description: scientific article; zbMATH DE number 5124993