Create accountLogin

Recent searches

No recent searches

Search options

Only available when logged in.
mathstodon.xyz is one of the many independent Mastodon servers you can use to participate in the fediverse.
A Mastodon instance for maths people. We have LaTeX rendering in the web interface!

Administered by:

Server stats:

2.9K
active users

mathstodon.xyz: AboutStatusProfiles directoryPrivacy policy

Mastodon: AboutGet the appKeyboard shortcutsView source codev4.3.7

Public
0xDE

@mjd You might already know that these numbers are really called Hadwiger numbers, but Claude obviously didn't. Relevant: section 8 of @DavidWood 's arxiv.org/abs/0711.1189

arXiv logo
arXiv.orgClique Minors in Cartesian Products of GraphsA "clique minor" in a graph G can be thought of as a set of connected subgraphs in G that are pairwise disjoint and pairwise adjacent. The "Hadwiger number" h(G) is the maximum cardinality of a clique minor in G. This paper studies clique minors in the Cartesian product G*H. Our main result is a rough structural characterisation theorem for Cartesian products with bounded Hadwiger number. It implies that if the product of two sufficiently large graphs has bounded Hadwiger number then it is one of the following graphs: - a planar grid with a vortex of bounded width in the outerface, - a cylindrical grid with a vortex of bounded width in each of the two `big' faces, or - a toroidal grid. Motivation for studying the Hadwiger number of a graph includes Hadwiger's Conjecture, which states that the chromatic number chi(G) <= h(G). It is open whether Hadwiger's Conjecture holds for every Cartesian product. We prove that if |V(H)|-1 >= chi(G) >= chi(H) then Hadwiger's Conjecture holds for G*H. On the other hand, we prove that Hadwiger's Conjecture holds for all Cartesian products if and only if it holds for all G * K_2. We then show that h(G * K_2) is tied to the treewidth of G. We also develop connections with pseudoachromatic colourings and connected dominating sets that imply near-tight bounds on the Hadwiger number of grid graphs (Cartesian products of paths) and Hamming graphs (Cartesian products of cliques).
Public
Mark Dominus

@11011110 @DavidWood I did not know that, thanks!

Public *
Mark Dominus

@11011110 @DavidWood I've been tinkering around with this since the 1980s; it seems it wasn't named after Hadwiger that long ago.

Public
0xDE

@mjd @DavidWood Alternative names:

"hadwiger number", B. Zelinka, "On Hadwiger number of a graph", Časopis pro pěstování matematiky, 1975, hdl.handle.net/10338.dmlcz/108

"contraction clique number", Bollobás, B.; Catlin, P. A.; Erdős, Paul (1980), "Hadwiger's conjecture is true for almost every graph" (PDF), European Journal of Combinatorics, 1 (3): 195–199, doi:10.1016/s0195-6698(80)80001-1.

"homomorphism degree", Halin, Rudolf (1976), "S-functions for graphs", Journal of Geometry, 8 (1–2): 171–186, doi:10.1007/BF01917434, MR 0444522, S2CID 120256194.

hdl.handle.netDML-CZ - Czech Digital Mathematics Library: On Hadwiger number of a graph
SearchLive feeds
About