Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949953 | Discrete Applied Mathematics | 2016 | 5 Pages |
Abstract
For a graph G, let G2 be the graph with the same vertex set as G and xyâE(G2) when xâ y and dG(x,y)â¤2. Bonamy, Lévêque, and Pinlou conjectured that if mad(G)<4â2c+1 and Î(G) is large, then Ïâ(G2)â¤Î(G)+c. We prove that if câ¥3, mad(G)<4â4c+1, and Î(G) is large, then Ïâ(G2)â¤Î(G)+c. DvoÅák, Král', Nejedlý, and Å krekovski conjectured that Ï(G2)â¤Î(G)+2 when Î(G) is large and G is planar with girth at least 5; our result implies Ï(G2)â¤Î(G)+6.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Matthew P. Yancey,