Hadwiger's conjecture for proper circular arc graphs
From MaRDI portal
(Redirected from Publication:1024291)
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.
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
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3706474 (Why is no real title available?)
- scientific article; zbMATH DE number 1156585 (Why is no real title available?)
- scientific article; zbMATH DE number 1432797 (Why is no real title available?)
- scientific article; zbMATH DE number 3232667 (Why is no real title available?)
- scientific article; zbMATH DE number 3358506 (Why is no real title available?)
- scientific article; zbMATH DE number 3102312 (Why is no real title available?)
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- A note on the Hadwiger number of circular arc graphs
- Algorithms on circular-arc graphs
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
- Coloring a Family of Circular Arcs
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Hadwiger's conjecture for line graphs
- Hadwiger's conjecture for powers of cycles and their complements
- Hajos' graph-coloring conjecture: Variations and counterexamples
- Matchings and Hadwiger's conjecture
- Matrix characterizations of circular-arc graphs
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
- On the structure of 5- and 6-chromatic abstract graphs.
- 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
- Structure theorems for some circular-arc graphs
- The Complexity of Coloring Circular Arcs and Chords
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 for the complements of Kneser graphs
- Hadwiger's conjecture and squares of chordal graphs
- Hadwiger's conjecture for circular colorings of edge-weighted 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)
