102,069 research outputs found
Hadwiger Number and Chromatic Number for Near Regular Degree Sequences
No full textWe consider a problem related to Hadwiger\u27s Conjecture. Let D=(d(1), d(2),...,d(n)) be a graphic sequence with 0 \u3c = d(1) \u3c = d(2) \u3c =...\u3c= d(n) \u3c = n-1. Any simple graph G with D its degree sequence is called a realization of D. Let R[D] denote the set of all realizations of D. Define h(D)=maxfh(G): G is an element of R[D]} and chi(D)=max{chi(G):G is an element of R[D]}, where h(G) and chi(G) are Hadwiger number and chromatic number of a graph G, respectively. Hadwiger\u27s Conjecture implies that h(D) \u3e =chi(D). In this paper, we establish the above inequality for near regular degree sequences. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 64: 175-183. 201
Hadwiger Number And Chromatic Number For Near Regular Degree Sequences
No full textWe consider a problem related to Hadwiger\u27s Conjecture. Let D=(d 1, d 2,...,d n) be a graphic sequence with 0≤d 1≤d 2≤···≤d n≤n-1. Any simple graph G with D its degree sequence is called a realization of D. Let R[D] denote the set of all realizations of D. Define h(D) = max{h(G): G∈R[D]} and χ(D) = max{χ(G):G∈R[D]}, where h(G) and χ(G) are Hadwiger number and chromatic number of a graph G, respectively. Hadwiger\u27s Conjecture implies that h(D)≥χ(D). In this paper, we establish the above inequality for near regular degree sequences. © 2009 Wiley Periodicals, Inc
Antipodal Hadwiger numbers of finite-dimensional Banach spaces
No full textLet X be a finite-dimensional Banach space; we introduce and investigate a natural generalization of the concepts of Hadwiger number H(X) and strict Hadwiger number H′(X). More precisely, we define the antipodal Hadwiger number Hα(X) as the largest cardinality of a subset S⊆ SX, such that ∀x≠y∈S∃f∈BX∗ with 1≤f(x)-f(y)andf(y)≤f(z)≤f(x)forz∈S.The strict antipodal Hadwiger number Hα′(X) is defined analogously. We prove that Hα′(X)=4 for every Minkowski plane and estimate (or in some cases compute) the numbers Hα(X) and Hα′(X), where X=ℓpn,1<p≤+∞ and n≥ 2. We also show that the number Hα′(X) grows exponentially in dim X. © 2020, The Managing Editors
Hadwiger Number of Graphs with Small Chordality
No full textThe Hadwiger number of a graph G is the largest integer h such that G has the complete graph Kh as a minor. We show that the problem of deter-mining the Hadwiger number of a graph is NP-hard on co-bipartite graphs, but can be solved in polynomial time on cographs and on bipartite permuta-tion graphs. We also consider a natural generalization of this problem that asks for the largest integer h such that G has a minor with h vertices and diameter at most s. We show that this problem can be solved in polynomial time on AT-free graphs when s ≥ 2, but is NP-hard on chordal graphs for every fixed s ≥ 2
Hadwiger Number of Graphs with Small Chordality
No full textInternational audienceThe Hadwiger number of a graph G is the largest integer h such that G has the complete graph K h as a minor. We show that the problem of determining the Hadwiger number of a graph is NP-hard on co-bipartite graphs, but can be solved in polynomial time on cographs and on bipartite permutation graphs. We also consider a natural generalization of this problem that asks for the largest integer h such that G has a minor with h vertices and diameter at most s. We show that this problem can be solved in polynomial time on AT-free graphs when s ≥ 2, but is NP-hard on chordal graphs for every fixed s ≥ 2
Hadwiger Number and the Cartesian Product of Graphs
No full textThe Hadwiger number eta(G) of a graph G is the largest integer n for which the complete graph K-n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, eta(G) >= chi(G), where chi(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product G square H of graphs.
As the main result of this paper, we prove that eta(G(1) square G(2)) >= h root 1 (1 - o(1)) for any two graphs G(1) and G(2) with eta(G(1)) = h and eta(G(2)) = l. We show that the above lower bound is asymptotically best possible when h >= l. This asymptotically settles a question of Z. Miller (1978).
As consequences of our main result, we show the following:
1. Let G be a connected graph. Let G = G(1) square G(2) square ... square G(k) be the ( unique) prime factorization of G. Then G satisfies Hadwiger's conjecture if k >= 2 log log chi(G) + c', where c' is a constant. This improves the 2 log chi(G) + 3 bound in [2] 2. Let G(1) and G(2) be two graphs such that chi(G1) >= chi(G2) >= clog(1.5)(chi(G(1))), where c is a constant. Then G1 square G2 satisfies Hadwiger's conjecture.
3. Hadwiger's conjecture is true for G(d) (Cartesian product of G taken d times) for every graph G and every d >= 2. This settles a question by Chandran and Sivadasan [2]. ( They had shown that the Hadiwger's conjecture is true for G(d) if d >= 3)
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds
No full textWe prove that the Hadwiger number of an n-vertex graph G (the maximum size of a clique minor in G) cannot be computed in time n^o(n), unless the Exponential Time Hypothesis (ETH) fails. This resolves a well-known open question in the area of exact exponential algorithms. The technique developed for resolving the Hadwiger number problem has a wider applicability. We use it to rule out the existence of n^o(n)-time algorithms (up to ETH) for a large class of computational problems concerning edge contractions in graphs
On a relationship between Hadwiger and stability numbers
No full textAbstractIn [2] it is proved that the inequality η(G)·(2α(G) − 1⩾ n(G) holds for any graph G where η(G) denotes the Hadwiger number of G, α(G) its stability number and n(G) its number of vertices, and it was conjectured the inequality η(G)·α(G) ⩾n(G) holds for every graph G. In this note, the graphs satisfying the equality case of the above mentioned theorem are characterized; an equivalent of the above conjecture is given and we define two parameters related to it and give their bound
Hadwiger Numbers and Gallai-Ramsey Numbers of Special Graphs
No full textThis dissertation explores two separate topics on graphs. We first study a far-reaching generalization of the Four Color Theorem. Given a graph G, we use chi(G) to denote the chromatic number; alpha(G) the independence number; and h(G) the Hadwiger number, which is the largest integer t such that the complete graph K_t can be obtained from a subgraph of G by contracting edges. Hadwiger\u27s conjecture from 1943 states that for every graph G, h(G) is greater than or equal to chi(G). This is perhaps the most famous conjecture in Graph Theory and remains open even for graphs G with alpha(G) less than or equal to 2. Let W_5 denote the wheel on six vertices. We establish more evidence for Hadwiger\u27s conjecture by proving that h(G) is greater than or equal to chi(G) for all graphs G such that alpha(G) is less than or equal to 2 and G does not contain W_5 as an induced subgraph. Our second topic is related to Ramsey theory, a field that has intrigued those who study combinatorics for many decades. Computing the classical Ramsey numbers is a notoriously difficult problem, leaving many basic questions unanswered even after more than 80 years. We study Ramsey numbers under Gallai-colorings. A Gallai-coloring of a complete graph is an edge-coloring such that no triangle is colored with three distinct colors. Given a graph H and an integer k at least 1, the Gallai-Ramsey number, denoted GR_k(H), is the least positive integer n such that every Gallai-coloring of K_n with at most k colors contains a monochromatic copy of H. It turns out that GR_k(H) is more well-behaved than the classical Ramsey number R_k(H), though finding exact values of GR_k(H) is far from trivial. We show that for all k at least 3, GR_k(C_{2n+1}) = n2^k+1 where n is 4, 5, 6 or 7, and GR_k(C_{2n+1}) is at most (n ln n)2^k-(k+1)n+1 for all n at least 8, where C_{2n+1} denotes a cycle on 2n+1 vertices
Generalized Hadwiger numbers for symmetric ovals
No full textSome estimations for the "juxtaposition function"
h
F
{h_F}
and an asymptotic formula for the function
h
F
/
h
G
{h_F}/{h_G}
, where
F
,
G
F,\;G
are central symmetric convex bodies, are given. Hadwiger and Grünbaum gave for
h
F
(
1
)
{h_F}(1)
the bounds
n
2
+
n
⩽
h
F
(
1
)
⩽
3
n
−
1
{n^2} + n \leqslant {h_F}(1) \leqslant {3^n} - 1
. Grünbaum conjectured (and proved for
n
=
2
n = 2
in Pacific J. Math. 11 (1961), 215-219) that for every even
r
r
between these bounds there exists in
E
n
{E^n}
an oval
F
F
such that
h
F
(
1
)
=
r
{h_F}(1) = r
. Lower bounds for
h
F
{h_F}
could be derived in the same way as in Theorems 1 and 2 from a good estimate of packing numbers on a Minkowski sphere, that is, from solutions to a Tammes-type problem in a Banch space.</p
- …
