Hadwiger's conjecture for graphs with forbidden holes

DOI10.1137/16M1086236MaRDI QIDQ5348213zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 14 August 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.06718

zbMATH Keywords

graph minorHadwiger's conjecturequasi-line graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76) Graph minors (05C83)

Abstract: Given a graph $G$, the Hadwiger number of $G$, denoted by $h(G)$, is the largest integer $k$ such that $G$ contains the complete graph $K_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)gechi(G)$, where $chi(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 $alpha(G)ge3$ has no hole of length between $4$ and $2alpha(G)-1$, then $h(G)gechi(G)$. We also prove that if a graph $G$ with independence number $alpha(G)ge2$ has no hole of length between $4$ and $2alpha(G)$, then $G$ contains an odd clique minor of size $chi(G)$, that is, such a graph $G$ satisfies the odd Hadwiger's conjecture.

Recommendations

• A note on Hadwiger's conjecture for \(W_5\)-free graphs with independence number two
• An approximate version of Hadwiger's conjecture for claw-free graphs
• Independence number and clique minors
• A special case of Hadwiger's conjecture
• Hadwiger's conjecture

Cites work

• A bound on the chromatic number of a graph
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• An approximate version of Hadwiger's conjecture for claw-free graphs
• Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
• Claw-free graphs. VII. Quasi-line graphs
• Clique minors in double-critical graphs
• Coloring graphs with forbidden minors
• Coloring quasi-line graphs
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Hadwiger's conjecture
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Hadwiger's conjecture for line graphs
• Hadwiger's conjecture for quasi-line graphs
• scientific article; zbMATH DE number 1156585 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• On a certain homomorphism properties of graphs II.
• On a special case of Hadwiger's conjecture
• On Certain Homomorphism Properties of Graphs I.
• On Seymour's strengthening of Hadwiger's conjecture for graphs with certain forbidden subgraphs
• On triangles in \(K_r\)-minor free graphs
• Some remarks on the odd Hadwiger's conjecture
• The Erdős-Lovász tihany conjecture for quasi-line graphs
• The four-colour theorem
• The strong perfect graph theorem

Cited in

(21)

• Clique immersions in graphs of independence number two with certain forbidden subgraphs
• Some remarks on even-hole-free graphs
• Erdős-Lovász Tihany conjecture for graphs with forbidden holes
• A note on Hadwiger's conjecture for \(W_5\)-free graphs with independence number two
• A special case of Hadwiger's conjecture
• Packing seagulls
• Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture
• Hadwiger's conjecture and squares of chordal graphs
• Hadwiger's conjecture for the complements of Kneser graphs
• Partial result on Hadwiger's conjecture
• An approximate version of Hadwiger's conjecture for claw-free graphs
• Forbidden configurations for hypohamiltonian graphs
• Hadwiger's conjecture for some hereditary classes of graphs: a survey
• On Hadwiger conjecture for certain families of graphs with restricted number of cycles
• NEWLY FOUND FORBIDDEN GRAPHS FOR TRIVIALIZABILITY
• Hadwiger's conjecture and topological bounds
• On Seymour's strengthening of Hadwiger's conjecture for graphs with certain forbidden subgraphs
• Odd clique minors in graphs with certain forbidden subgraphs
• Odd clique minors and chromatic bounds of {\(3K_1\), paraglider}-free graphs
• Clique minors in claw-free graphs
• Hadwiger's conjecture for powers of cycles and their complements

This page was built for publication: Hadwiger's conjecture for graphs with forbidden holes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5348213)