Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Hadwiger’s conjecture for proper circular arc graphs
Belkale N., Chandran L. European Journal of Combinatorics30 (4):946-956,2009.Type:Article
Date Reviewed: Sep 28 2009

The arcs of a circle represent the vertex sets of circular graphs: “Two vertices are adjacent if and only if their corresponding arcs intersect.” A circular graph is proper if no arc representing a vertex is contained properly in another arc representing a vertex.

Hadwiger’s conjecture states that if the chromatic number of a graph G equals r, then the complete graph on r vertices is a minor of G. This paper addresses Hadwiger’s conjecture for proper circular graphs. In a series of lemmas, it is shown that this “conjecture is true for proper circular arc graphs.”

The proof uses clever combinatorial arguments. Proving this conjecture for the class of proper circular graphs is important on its own, but circular graphs are also important mathematical objects with many applications--for example, in statistics and computer science (CS).

Reviewer:  Jan De Beule Review #: CR137328 (1004-0400)
Bookmark and Share
  Featured Reviewer  
 
Graph Labeling (G.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Labeling": Date
Bounding the bandwidths for graphs
Zhou S. Theoretical Computer Science 249(2): 357-368, 2000. Type: Article
Apr 22 2002
Graph recurrence: how to write them and why
Vince A. European Journal of Combinatorics 24(1): 15-32, 2003. Type: Article
Jul 2 2003
Distance labeling in graphs
Gavoille C., Peleg D., Pérennes S., Raz R. Journal of Algorithms 53(1): 85-112, 2004. Type: Article
Jan 26 2005
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy