Two smaller upper bounds of list injective chromatic number

详细信息    查看全文

• 作者：Yuehua Bu (1)
  Kai Lu (1)
  Sheng Yang (1)
  
  1. Department of Mathematics ; Zhejiang Normal University ; Jinhua ; 321004 ; China
  
• 关键词：Injective coloring ; Maximum degree ; Cycles ; Maximum average degree
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：29
• 期：2
• 页码：373-388
• 全文大小：303 KB
• 参考文献：1. Borodin OV, Ivanova AO (2011) Injective $(\Delta +1)$-coloring of planar graphs with girth 6. Siberian Math J 52:23鈥?9 CrossRef
  2. Borodin OV, Ivanova AO (2011) List injective colorings of planar graphs. Discret Math 311:154鈥?65 CrossRef
  3. Borodin OV, Ivanova AO, Neustroeva TK (2007) A prescribed 2-distance $(\Delta +1)$-coloring of planar graphs with a given girth. Diskretn Anal Issled Oper Ser 1 14(3):13鈥?0
  4. Bu Y, Chen D, Raspaud A, Wang W (2009) Injective coloring of planar graphs. Discret Appl Math 157:663鈥?72 CrossRef
  5. Bu Y, Lu K (2012) Injective colorings of planar graphs with girth 7. Discret Math. Algorithms Appl 4(2), 1250034, p. 8
  6. Chen M, Hahn G, Raspaud A, Wang W (2012) Some results on the injective chromatic number of graphs. J Comb Optim 24:299鈥?18 CrossRef
  7. Cranston DW, Kim S-J, Yu G (2010) Injective colorings of sparse graphs. Discret Math 310:2965鈥?973 CrossRef
  8. Cranston DW, Kim S-J, Yu G (2010) Injective colorings of graphs with low average degreee. Algorithmica 60:553鈥?68 CrossRef
  9. Dimitrov D, Lu啪ar B, 艩krekovski R (2009) Injective coloring of planar graphs, manuscript. http://topology.nipissingu.ca/graph2010/abstracts/abstract_DD_InjectiveColoring.pdf
  10. Doyon A, Hahn G, Raspaud A (2010) Some bounds on the injective chromatics number of graphs. Discret Math 310:585鈥?90 CrossRef
  11. Dong A, Wang G (2012) Neighbor sum distinguishing coloring of some graphs. Discret Math. Algorithms Appl 4(4), 1250047, p. 12
  12. Hahn G, Kratochv铆l J, 艩ir谩艌 J, Sotteau D (2002) On the injective chromatic number of graphs. Discret Math 256:179鈥?92
  13. Hahn G, Raspaud A, Wang W (2006) On the injective coloring of $K_{4}$-minor free graphs, preprint
  14. Li R, Xu B (2012) Injective choosability of planar graphs of girth five and six. Discret Math 312:1260鈥?265 CrossRef
  15. Lu啪ar B (2010) Planar graphs with largest injective chromatic numbers. IMFM Preprint Series 48:1110
  16. Lu啪ar B, 艩krekovski R, Tancer M (2009) Injective colorings of planar graphs with few colors. Discret Math 309:5636鈥?649 CrossRef
  17. Paul V, Germina KA (2012) On edge coloring of hypergraphs and Erd枚s-Faber-Lov谩sz conjecture. Discret Math, Algorithms Appl 4(1), 125003, p. 5
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

An injective coloring of a graph \(G\) is an assignment of colors to the vertices of \(G\) so that any two vertices with a common neighbor receive distinct colors. Let \(\chi _{i}^{l}(G)\) denote the list injective chromatic number of \(G\) . We prove that (1) \(\chi _{i}^{l}(G)=\Delta \) for a graph \(G\) with the maximum average degree \(Mad(G)\le \frac{18}{7}\) and maximum degree \(\Delta \ge 9\) ; (2) \(\chi _{i}^{l}(G)\le \Delta +2\) if \(G\) is a plane graph with \(\Delta \ge 21\) and without 3-, 4-, 8-cycles.