Connectivity of Minimum Non-5-injectively Colorable Planar Cubic Graphs

doi:10.1007/s40305-018-0214-6

Journal of the Operations Research Society of China ›› 2020, Vol. 8 ›› Issue (1): 105-116.doi: 10.1007/s40305-018-0214-6

收稿日期:2017-10-12 修回日期:2018-04-09 出版日期:2020-03-30 发布日期:2020-02-18
通讯作者: Jing Jin, Bao-Gang Xu E-mail:jinjing19841@126.com;baogxu@njnu.edu.cn
基金资助:
This research was supported by the National Natural Science Foundation of China (Nos. 11571180 and 11331003), and the Natural Science Foundation of Jiangsu Higher Education Institutions of China (No. 17KJB110010).

Connectivity of Minimum Non-5-injectively Colorable Planar Cubic Graphs

Jing Jin^1,2, Bao-Gang Xu¹

1 Institute of Mathematics, School of Mathematical Sciences, Nanjing Normal University, Nanjing 210023, China;
2 College of Taizhou, Nanjing Normal University, Taizhou 225300, Jiangsu, China

Received:2017-10-12 Revised:2018-04-09 Online:2020-03-30 Published:2020-02-18
Contact: Jing Jin, Bao-Gang Xu E-mail:jinjing19841@126.com;baogxu@njnu.edu.cn

摘要/Abstract

Abstract: Suppose that G is a planar cubic graph with χ_i(G)> 5. We show that if χ_i(H) <χ_i(G) for each planar cubic graph H of order less than G, then G is either a 3-connected simple planar cubic graph, or a planar graph obtained from a simple cubic 3-connected planar graph by adding some earrings. This shows that a minimum non-5-injectively colorable simple planar cubic graph must be 3-connected.

Key words: Planar cubic graphs, Connectivity, 3-connected, Injective coloring

中图分类号:

05C15
05C35

. [J]. Journal of the Operations Research Society of China, 2020, 8(1): 105-116.

Jing Jin, Bao-Gang Xu. Connectivity of Minimum Non-5-injectively Colorable Planar Cubic Graphs[J]. Journal of the Operations Research Society of China, 2020, 8(1): 105-116.

参考文献

[1] Hahn, G., Kratochvíl, J., KŠiráň, J., Sotteau, D.:On the injective chromatic number of graphs. Discrete Math. 256, 179-192(2002)
[2] Hell, P., Raspaud, A., Stacho, J.:On injective colourings of chordal graphs. In:Lecture Notes in Computer Science, vol. 4957, p. 520(2008)
[3] Jin, J., Xu, B., Zhang, X.:On the complexity of injective colorings and its generalizations. Theor. Comput. Sci. 491, 119-126(2013)
[4] Bu, Y., Chen, D., Raspaud, A., Wang, W.:Injective coloring of planar graphs. Discrete Appl. Math. 157, 663-672(2009)
[5] Cranston, D.W., Kim, S.-J., Yu, G.:Injective colorings of sparse graphs. Discrete Math. 310, 2965-2973(2010)
[6] Cranston, D.W., Kim, S.-J., Yu, G.:Injective colorings of graphs with low average degree. Algorithmica 60, 553-568(2011)
[7] Dong, W., Lin, W.:Injective coloring of planar graphs with girth 6. Discrete Math. 313, 1302-1311(2013)
[8] Doyon, A., Hahn, G., Raspaud, A.:Some bounds on the injective chromatic number of graphs. Discrete Math. 310, 585-590(2010)
[9] Borodin, O., Ivanova, A.:List injective colorings of planar graphs. Discrete Math. 311, 154-165(2011)
[10] Bu, Y., Lu, K.:List injective coloring of planar graphs with girth 5, 6, 8. Discrete Appl. Math. 161, 1367-1377(2013)
[11] Bu, Y., Lu, K., Yang, S.:Two smaller upper bounds of list injective chromatic number. J. Comb. Optim. 29, 373-388(2015)
[12] Li, R., Xu, B.:Injective choosability of planar graphs of girth five and six. Discrete Math. 312, 1260-1265(2012)
[13] Chen, M., Hahn, G., Raspaud, A., Wang, W.:Some results on the injective chromatic number of graphs. J. Comb. Optim. 24, 299-318(2012)
[14] Lužar, B., Škrekovski, R.:Counterexamples to a conjecture on injective coloring. Ars Math. Contemp. 8, 291-295(2015)
[15] Wegner, G.:Graphs with given diameter and a coloring problem. Technical report, University of Dortmund, Germany (1977)
[16] Thomassen, C.:The square of a planar cubic graph is 7-colorable. J. Comb. Theory Ser. B 128, 192-218(2018)
[17] Cranston, D.W., Kim, S.-J.:List-coloring the square of a subcubic graph. J. Graph Theory 57, 65-87(2008)
[18] Hartke, S.G., Jahanbekam, S., Thomas, B.:The chromatic number of the square of subcubic planar graphs (2016). arXiv:1604.06504v1[math.CO]
[19] Lužar, B., Škrekovski, R., Tancer, M.:Injective colorings of planar graphs with few colors. Discrete Math. 309, 5636-5649(2009)
[20] Dirac, G.A.:Some theorems on abstract graphs. Proc. Lond. Math. Soc. 2(3), 69-81(1952)

Connectivity of Minimum Non-5-injectively Colorable Planar Cubic Graphs

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价