Hadwiger'S Conjecture For Graphs With Forbidden Holes

Keywords

Graph minor; Hadwiger's conjecture; Quasi-line graph

Abstract

Given a graph G, the Hadwiger number of G, denoted by h(G), is the largest integer κ such that G contains the complete graph Kκ as a minor. A hole in G is an induced cycle of length at least four. Hadwiger's conjecture from 1943 states that for every graph G, h(G) ≥ X(G), where X(G) denotes the chromatic number of G. In this paper we establish more evidence for Hadwiger's conjecture by showing that if a graph G with independence number α(G) ≥ 3 has no hole of length between 4 and 2α(G) - 1, then h(G) ≥ X(G). We also prove that if a graph G with independence number α(G) ≥ 2 has no hole of length between 4 and 2α(G), then G contains an odd clique minor of size X(G), that is, such a graph G satises the odd Hadwiger's conjecture.

Publication Date

1-1-2017

Publication Title

SIAM Journal on Discrete Mathematics

Volume

31

Issue

3

Number of Pages

1572-1580

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1137/16M1086236

Socpus ID

85031711694 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS