首页 | 本学科首页   官方微博 | 高级检索  
     


A note on the Hadwiger number of circular arc graphs
Authors:N.S. Narayanaswamy  N. Sivadasan
Affiliation:a Department of Computer Science and Engineering, Indian Institute of Technology, Chennai 600036, India
b CSA Department, Indian Institute of Science, Bangalore 560012, India
c Strand Genomics, 237, Sir. C.V. Raman Avenue, Rajmahal Vilas, Bangalore 560080, India
Abstract:The intention of this note is to motivate the researchers to study Hadwiger's conjecture for circular arc graphs. Let η(G) denote the largest clique minor of a graph G, and let χ(G) denote its chromatic number. Hadwiger's conjecture states that η(G)?χ(G) and is one of the most important and difficult open problems in graph theory. From the point of view of researchers who are sceptical of the validity of the conjecture, it is interesting to study the conjecture for graph classes where η(G) is guaranteed not to grow too fast with respect to χ(G), since such classes of graphs are indeed a reasonable place to look for possible counterexamples. We show that in any circular arc graph G, η(G)?2χ(G)−1, and there is a family with equality. So, it makes sense to study Hadwiger's conjecture for this family.
Keywords:Circular arc   Hadwiger's conjecture   Minor   Graph coloring   Combinatorial problems
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号