Simultaneous coloring of vertices and incidences of outerplanar graphs
Abstract
A vi-simultaneous proper k-coloring of a graph G is a coloring of all vertices and incidences of the graph in which any two adjacent or incident elements in the set V(G)∪I(G) receive distinct colors, where I(G) is the set of incidences of G. The vi-simultaneous chromatic number, denoted by χvi(G), is the smallest integer k such that G has a vi-simultaneous proper k-coloring. In [M. Mozafari-Nia, M. N. Iradmusa, A note on coloring of 3/3-power of subquartic graphs, Vol. 79, No.3, 2021] vi-simultaneous proper coloring of graphs with maximum degree 4 is investigated and they conjectured that for any graph G with maximum degree Δ ≥ 2, vi-simultaneous proper coloring of G is at most 2Δ + 1. In [M. Mozafari-Nia, M. N. Iradmusa, Simultaneous coloring of vertices and incidences of graphs, arXiv:2205.07189, 2022] the correctness of the conjecture for some classes of graphs such as k-degenerated graphs, cycles, forests, complete graphs, regular bipartite graphs is investigated. In this paper, we prove that the vi-simultaneous chromatic number of any outerplanar graph G is either Δ + 2 or Δ + 3, where Δ is the maximum degree of G.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2023.11.1.20
References
I. Algor, N. Alon, The Star Arboricity of Graphs, Discrete Mathematics 43 (1989), 11–22.
M. Behzad, Graphs and their Chromatic Numbers, Ph.D. thesis, Michigan State University, 1965.
J. A. Bondy and U. S. R. Murty, Graph theory, Graduate Texts in Mathematics 244, Springer, New York, 2008.
O. V. Borodin, Structural theorem on plane graphs with application to the entire coloring number, J. Graph Theory 23 (1996), 233–239.
O. V. Borodin, Simultaneous coloring of edges and faces of plane graphs, Discrete Math. 128 (1994), 21–33.
O. V. Borodin, Solution of Ringel’s problems of the face and vertex coloring of plane graphs and coloring of 1-planar graphs, Metody Diskret. Analiza 41 (1984), 12–26 (in Russian).
R. A. Brualdi and J. Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993), 51–58.
Min Chen, J. Yang, Hao Zhang, Y. Wang, Weakly entire coloring of outerplanar graphs, Oper. Res. Trans. 25 (2021), 132–136.
J. Fiamcik, Simultaneous colouring of 4-valent maps, Mat. Casopis Sloven. Akad. Vied 21 (1971), 9–13.
Miroslav Fiedler, Recent advances in graph theory, Proceedings of the Second Czechoslovak Symposium held in Prague, Prague, 544 pages, 1975.
E, Jucovic, On a problem in map colouring, Mat. Casopis Sloven. Akad. Vied 19 (1969), 225–227, errata, ibid. 20 (1970), 224.
H. V. Kronk, J. Mitchem, A seven-color theorem on the sphere, Discrete Math. 5 (1973), 253–260.
M. N. Iradmusa, On colorings of graph fractional powers, Discrete Math. 310 (2010), 1551–1556.
M. Mozafari-Nia, M. N. Iradmusa, A note on coloring of 3/3-power of subquartic graphs, Australasian J. of Combinatorics 79 (2021), 454–460.
M. Mozafari-Nia, M. N. Iradmusa, Simultaneous coloring of vertices and incidences of graphs, submitted (2021), https://arxiv.org/abs/2205.07189.
M. Mozafari-Nia, Behnaz Omoomi, Injective chromatic number of outerplanar graphs, Taiwanese Journal of Mathematics 22 (2018), 1309–1320.
Gerhard Ringel, Das Geschlecht des vollständigen paaren Graphen, (German) Abh. Math. Sem. Univ. Hamburg 28 (1965), 139–150.
D. P. Sanders, Y. Zhao, On the entire colouring conjecture, Canad. Math. Bull. 43 (2000), 108–114.
Adrian O. Waller, Simultaneously colouring the edges and faces of plane graphs, J. Combin. Theory Ser. B 69 (1997), 219–221.
F. Wang and X. Liu, Coloring 3-power of 3-subdivision of subcubic graph, Discrete Mathematics, Algorithms and Applications 10 (3), 1850041 (2018).
W. Wang and J. Liu, On the vertex face total chromatic number of planar graphs, J. Graph Theory 22 (1996), 29–37.
W. Wang and Xuding Zhu, Entire colouring of plane graphs, Journal of Combinatorial Theory, Series B 101 (2011), 490–501.
D. B. West, Introduction to graph theory, Prentice Hall, Second edition, 2001.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.