On t -Relaxed 2-Distant Circular Coloring of Graphs
- PDF / 861,255 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 89 Downloads / 188 Views
On t-Relaxed 2-Distant Circular Coloring of Graphs Dan He1 · Wensong Lin1 Received: 12 December 2019 / Revised: 3 October 2020 / Accepted: 9 October 2020 © Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia 2020
Abstract Let k be a positive integer. For any two integers i and j in {0, 1, . . . , k − 1}, let |i − j|k be the circular distance between i and j, which is defined as min{|i − j|, k − |i − j|}. Suppose f is a mapping from V (G) to {0, 1, . . . , k−1}. If, for any two adjacent vertices u and v in V (G), | f (u) − f (v)|k ≥ 2, then f is called a k2 -coloring of G. In this paper, we study the relaxation of 2k -coloring. If adjacent vertices receive different integers, and for each vertex u of G, the number of neighbors v of u with | f (u) − f (v)|k = 1 is at most t, then f is called a t-relaxed 2-distant circular k-coloring, or simply a ( k2 , t)∗ coloring of G. If G has a ( k2 , t)∗ -coloring, then G is called ( k2 , t)∗ -colorable. We prove that, for any two fixed integers k and t with k ≥ 2 and t ≥ 1, the problem of deciding whether a graph G is ( k2 , t)∗ -colorable is NP-complete except the case k = 2 and the case k = 3 and t ≤ 3, which are polynomially solvable. For any outerplanar graph G, it is easy to see that G is ( 26 , 0)∗ -colorable. We show that all outerplanar graphs are ( 25 , 4)∗ -colorable, and there is no fixed positive integer t such that all outerplanar graphs are ( 24 , t)∗ -colorable. Keywords Circular coloring · 2-Distant coloring · t-Relaxed 2-distant circular coloring · Defective circular coloring · Outerplanar graph · NP-complete Mathematics Subject Classification 05C15
Communicated by Sanming Zhou. This work was supported by NSFC 11701080 and 11771080.
B
Wensong Lin [email protected] Dan He [email protected]
1
School of Mathematics, Southeast University, Nanjing 210096, People’s Republic of China
123
D. He, W. Lin
1 Introduction In this paper, we focus on undirected and simple graphs, and we use standard notations in graph theory (cf. [3]). The circular chromatic number of a graph is a natural generalization of the chromatic number of a graph. In [24], Zhu gave the definition of circular coloring by introducing the problem of designing a traffic control system. At a road intersection, each traffic flow is assigned an interval of time during which it faces a green light. A complete traffic period is a time interval during which each traffic flow gets a turn of green light. It needs to design a red-green light pattern for a complete traffic period, and the pattern will be repeated forever. Assume that each interval of green light has unit length. The problem of designing a traffic control system is to minimize the total length of a complete traffic period. The problem of designing a traffic control system can be modeled as a kind of graph coloring problem. We use vertices of a graph to denote the traffic flow, and two vertices are adjacent if the corresponding traffic flows are not compatible, which means their green light intervals must not overl
Data Loading...
