Simultaneous coloring of vertices and incidences of outerplanar graphs

被引:2
作者
Mozafari-Nia, Mahsa [1 ]
Iradmusa, Moharram N. [1 ,2 ]
机构
[1] Shahid Beheshti Univ, Dept Math Sci, POB 19839-63113, Tehran, Iran
[2] Inst Res Fundamental Sci IPM, Sch Math, POB 19395-5746, Tehran, Iran
关键词
incidence of graph; simultaneous coloring of graph; outerplanar graph; CHROMATIC NUMBER; PLANE; FACES; EDGES;
D O I
10.5614/ejgta.2023.11.1.20
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 chi 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 33-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 increment >= 2, vi-simultaneous proper coloring of G is at most 2 increment + 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 increment + 2 or increment + 3, where increment is the maximum degree of G.
引用
收藏
页码:245 / 262
页数:18
相关论文
共 24 条
  • [1] THE STAR ARBORICITY OF GRAPHS
    ALGOR, I
    ALON, N
    [J]. DISCRETE MATHEMATICS, 1989, 75 (1-3) : 11 - 22
  • [2] Behzad M., 1965, Graphs and their Chromatic Numbers
  • [3] Bondy J.A., 2008, GRADUATE TEXTS MATH, V244, DOI DOI 10.1007/978-1-84628-970-5
  • [4] Borodin O. V., 1984, METODY DISKRET ANAL, V108, P12
  • [5] Borodin OV, 1996, J GRAPH THEOR, V23, P233, DOI 10.1002/(SICI)1097-0118(199611)23:3<233::AID-JGT3>3.3.CO
  • [6] 2-I
  • [7] SIMULTANEOUS COLORING OF EDGES AND FACES OF PLANE GRAPHS
    BORODIN, OV
    [J]. DISCRETE MATHEMATICS, 1994, 128 (1-3) : 21 - 33
  • [8] INCIDENCE AND STRONG EDGE COLORINGS OF GRAPHS
    BRUALDI, RA
    MASSEY, JJQ
    [J]. DISCRETE MATHEMATICS, 1993, 122 (1-3) : 51 - 58
  • [9] [陈敏 Chen Min], 2021, [运筹学学报, Operations Research Transaction], V25, P132
  • [10] Fiamcik J., 1971, MAT CASOPIS SLOVEN A, V21, P9