Title

Some Remarks On The Odd Hadwiger'S Conjecture

Abstract

We say that H has an odd complete minor of order at least l if there are l vertex disjoint trees in H such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic. Gerards and Seymour conjectured that if a graph has no odd complete minor of order l, then it is (l - 1)-colorable. This is substantially stronger than the well-known conjecture of Hadwiger. Recently, Geelen et al. proved that there exists a constant c such that any graph with no odd K k -minor is ck√log k-colorable. However, it is not known if there exists an absolute constant c such that any graph with no odd K k -minor is ck-colorable. Motivated by these facts, in this paper, we shall first prove that, for any k, there exists a constant f(k) such that every (496k + 13)-connected graph with at least f(k) vertices has either an odd complete minor of size at least k or a vertex set X of order at most 8k such that G-X is bipartite. Since any bipartite graph does not contain an odd complete minor of size at least three, the second condition is necessary. This is an analogous result of Böhme et al. We also prove that every graph G on n vertices has an odd complete minor of size at least n/2α(G) - 1, where α(G) denotes the independence number of G. This is an analogous result of Duchet and Meyniel. We obtain a better result for the case α(G)= 3. © 2007 Springer-Verlag.

Publication Date

7-1-2007

Publication Title

Combinatorica

Volume

27

Issue

4

Number of Pages

429-438

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s00493-007-2213-9

Socpus ID

44449146026 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/44449146026

This document is currently not available here.

Share

COinS