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

Previous Articles Next Articles

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

CLC Number:

05C15
05C35

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.

TrendMD

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	Hui Shang, Eminjan Sabir, Ji-Xiang Meng. Conditional Edge Connectivity of the Locally Twisted Cubes [J]. Journal of the Operations Research Society of China, 2019, 7(3): 501-509.
[2]	Han－Yuan Deng · He Huang · Jie Zhang. On the Eigenvalues of General Sum-Connectivity Laplacian Matrix [J]. Journal of the Operations Research Society of China, 2013, 1(3): 347-358.