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.
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
.
DOI: 10.1007/s40305-018-0214-6
[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)
