Hadwiger's conjecture for proper circular arc graphs
From MaRDI portal
Publication:1024291
DOI10.1016/J.EJC.2008.07.024zbMATH Open1205.05212arXivmath/0605503OpenAlexW2070544104WikidataQ123237737 ScholiaQ123237737MaRDI QIDQ1024291FDOQ1024291
Naveen Belkale, L. Sunil Chandran
Publication date: 17 June 2009
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Abstract: Circular arc graphs are graphs whose vertices can be represented as arcs on a circle such that any two vertices are adjacent if and only if their corresponding arcs intersect. Proper circular arc graphs are graphs which have a circular arc representation where no arc is completely contained in any other arc. Hadwiger's conjecture states that if a graph has chromatic number , then a complete graph of vertices is a minor of . We prove Hadwiger's conjecture for proper circular arc graphs.
Full work available at URL: https://arxiv.org/abs/math/0605503
Recommendations
- A note on the Hadwiger number of circular arc graphs
- Hadwiger's conjecture for 3-arc graphs
- Hadwiger's conjecture for circular colorings of edge-weighted graphs
- On chordal proper circular arc graphs
- Proper Helly Circular-Arc Graphs
- Hadwiger's conjecture for line graphs
- Circular-arc hypergraphs: rigidity via connectedness
- Essential obstacles to Helly circular-arc graphs
- On some subclasses of circular-arc graphs
- On the isomorphism problem for Helly circular-arc graphs
Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Graph minors (05C83)
Cites Work
- Title not available (Why is that?)
- The Complexity of Coloring Circular Arcs and Chords
- Algorithms on circular-arc graphs
- SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
- Title not available (Why is that?)
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- Structure theorems for some circular-arc graphs
- Coloring a Family of Circular Arcs
- Matrix characterizations of circular-arc graphs
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- Hajos' graph-coloring conjecture: Variations and counterexamples
- Hadwiger's conjecture for line graphs
- Title not available (Why is that?)
- A note on the Hadwiger number of circular arc graphs
- On the structure of 5- and 6-chromatic abstract graphs.
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- Title not available (Why is that?)
- Hadwiger's conjecture for powers of cycles and their complements
- Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
- Matchings and Hadwiger's conjecture
- Revisiting Tucker's Algorithm to Color Circular Arc Graphs
- Title not available (Why is that?)
Cited In (10)
- Boxicity of circular arc graphs
- Hadwiger's conjecture for squares of 2-trees
- A note on the Hadwiger number of circular arc graphs
- On the hyperbolicity constant of circular-arc graphs
- Hadwiger's conjecture for 3-arc graphs
- Hadwiger’s Conjecture and Squares of Chordal Graphs
- Hadwiger's conjecture for circular colorings of edge-weighted graphs
- Hadwiger's Conjecture for the Complements of Kneser Graphs
- Weakening total coloring conjecture and Hadwiger's conjecture on total graphs
- Circular-arc hypergraphs: rigidity via connectedness
This page was built for publication: Hadwiger's conjecture for proper circular arc graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024291)
