Hadwiger's conjecture for proper circular arc graphs

DOI10.1016/j.ejc.2008.07.024zbMath1205.05212arXivmath/0605503OpenAlexW2070544104WikidataQ123237737 ScholiaQ123237737MaRDI QIDQ1024291

Naveen Belkale, L. Sunil Chandran

Publication date: 17 June 2009

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

minorHadwiger conjectureproper circular arc graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Related Items

Hadwiger's conjecture for squares of 2-trees ⋮ A note on the Hadwiger number of circular arc graphs ⋮ Weakening total coloring conjecture and Hadwiger's conjecture on total graphs ⋮ Hadwiger's Conjecture for the Complements of Kneser Graphs ⋮ Boxicity of circular arc graphs ⋮ Hadwiger's conjecture for 3-arc graphs ⋮ Hadwiger’s Conjecture and Squares of Chordal Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hadwiger's conjecture for powers of cycles and their complements
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Matchings and Hadwiger's conjecture
• Hadwiger's conjecture for line graphs
• A note on the Hadwiger number of circular arc graphs
• Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
• Matrix characterizations of circular-arc graphs
• Structure theorems for some circular-arc graphs
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Algorithms on circular-arc graphs
• Coloring a Family of Circular Arcs
• Revisiting Tucker's Algorithm to Color Circular Arc Graphs
• SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
• On the structure of 5- and 6-chromatic abstract graphs.
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs