O. V. Borodin, A. O. Ivanova, “Injective $(\Delta+1)$-coloring of planar graphs with girth 6”, Sibirsk. Mat. Zh., 52:1 (2011), 30–38; Siberian Math. J., 52:1 (2011), 23

Loading [MathJax]/jax/output/CommonHTML/jax.js

Sibirskii Matematicheskii Zhurnal

RUS ENG

JOURNALS PEOPLE ORGANISATIONS CONFERENCES SEMINARS VIDEO LIBRARY PACKAGE AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	General information
	Latest issue
	Archive
	Impact factor

	Search papers
	Search references

	RSS
	Latest issue
	Current issues
	Archive issues
	What is RSS

Sibirsk. Mat. Zh.:
Year:
Volume:
Issue:
Page:
	Find

Personal entry:
Login:
Password:
	Save password
	Enter
	Forgotten password?
	Register

Sibirskii Matematicheskii Zhurnal, 2011, Volume 52, Number 1, Pages 30–38 (Mi smj2175)

This article is cited in 17 scientific papers (total in 17 papers)

Injective

$(\Delta+1)$ -coloring of planar graphs with girth 6

O. V. Borodin^a, A. O. Ivanova^b

^a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
^b Institute for Mathematics and Informatics, Yakutsk State University, Yakutsk

Full-text PDF (318 kB) Citations (17)

References:

PDF

HTML

Abstract: A vertex coloring of a graph

$G$ is called injective if every two vertices joined by a path of length 2 get different colors. The minimum number

$\chi_i(G)$ of the colors required for an injective coloring of a graph

$G$ is clearly not less than the maximum degree

$\Delta(G)$ of

$G$ . There exist planar graphs with girth

$g\ge6$ and

$\chi_i=\Delta+1$ for any

$\Delta\ge2$ . We prove that every planar graph with

$\Delta\ge18$ and

$g\ge6$ has

$\chi_i\le\Delta+1$ .

Keywords: planar graph, injective coloring, girth.

Received: 03.02.2010

English version:
Siberian Mathematical Journal, 2011, Volume 52, Issue 1, Pages 23–29
DOI: https://doi.org/10.1134/S0037446606010034

Bibliographic databases:

Document Type: Article

UDC: 519.17

Language: Russian

Citation: O. V. Borodin, A. O. Ivanova, “Injective

$(\Delta+1)$ -coloring of planar graphs with girth 6”, Sibirsk. Mat. Zh., 52:1 (2011), 30–38; Siberian Math. J., 52:1 (2011), 23–29

Citation in format AMSBIB

\Bibitem{BorIva11}

\by O.~V.~Borodin, A.~O.~Ivanova

\paper Injective $(\Delta+1)$-coloring of planar graphs with girth~6

\jour Sibirsk. Mat. Zh.

\yr 2011

\vol 52

\issue 1

\pages 30--38

\mathnet{http://mi.mathnet.ru/smj2175}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2810248}

\transl

\jour Siberian Math. J.

\yr 2011

\vol 52

\issue 1

\pages 23--29

\crossref{https://doi.org/10.1134/S0037446606010034}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000288172400003}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-79952430442}

Linking options:

https://www.mathnet.ru/eng/smj2175

https://www.mathnet.ru/eng/smj/v52/i1/p30

This publication is cited in the following 17 articles:

Ying Chen, Lan Tao, Li Zhang, “Injective Δ+2 Coloring of Planar Graph Without Short Cycles”, Acta Math. Appl. Sin. Engl. Ser., 39:4 (2023), 1009
Qiming Fang, Li Zhang, “Sharp upper bound of injective coloring of planar graphs with girth at least 5”, J Comb Optim, 44:2 (2022), 1161
Yuehua B., Chentao Q., Junlei Zh., Ting X., “Injective Coloring of Planar Graphs”, Theor. Comput. Sci., 857 (2021), 114–122
Bu Yuehua, Qi Chentao, Zhu Junlei, Lecture Notes in Computer Science, 12290, Algorithmic Aspects in Information and Management, 2020, 492
Mozafari-Nia M., Omoomi B., “Injective Chromatic Number of Outerplanar Graphs”, Taiwan. J. Math., 22:6 (2018), 1309–1320
Bu Yu., Wang Ch., Yang Sh., “List Injective Coloring of Planar Graphs”, ARS Comb., 141 (2018), 191–211
Bu Yu., Qi Ch., “Injective Edge Coloring of Sparse Graphs”, Discret. Math. Algorithms Appl., 10:2 (2018), 1850022
W. Dong, B. Xu, “2-distance coloring of planar graphs with girth $5$ ”, J. Comb. Optim., 34:4 (2017), 1302–1322
H.-Yu. Chen, J.-L. Wu, “List injective coloring of planar graphs with girth $G \ge 6$ ”, Discrete Math., 339:12 (2016), 3043–3051
Yu. Bu, K. Lu, Sh. Yang, “Two smaller upper bounds of list injective chromatic number”, J. Comb. Optim., 29:2 (2015), 373–388
B. Luzar, R. Skrekovski, “Counterexamples to a conjecture on injective colorings”, ARS Math. Contemp., 8:2 (2015), 291–295
M. Bonamy, B. Leveque, A. Pinlou, “Graphs with maximum degree $\Delta \ge 17$ and maximum average degree less than $3$ are list $2$ -distance $(\Delta+2)$ -colorable”, Discrete Math., 317 (2014), 19–32
YUEHUA BU, SHENG YANG, “LIST INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH g ≥ 5”, Discrete Math. Algorithm. Appl., 06:01 (2014), 1450006
O. V. Borodin, “Colorings of plane graphs: a survey”, Discrete Math., 313:4 (2013), 517–539
Yu. Bu, K. Lu, “List injective coloring of planar graphs with girth $5, 6, 8$ ”, Discrete Appl. Math., 161:10-11 (2013), 1367–1377
W. Dong, W. Lin, “Injective coloring of planar graphs with girth $6$ ”, Discrete Math., 313:12 (2013), 1302–1311
YUEHUA BU, KAI LU, “INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH 7”, Discrete Math. Algorithm. Appl., 04:02 (2012), 1250034

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Statistics & downloads:
Abstract page:	448
Full-text PDF :	112
References:	67
First page:	1

Что такое QR-код?

Registration to the website

Logotypes