Abstract
Let T be a T-set, i.e., a finite set of nonnegative integers satisfying 0 ∈ T, and G be a graph. In the paper we study relations between the T-edge spans espT (G) and espd⊙T (G), where d is a positive integer and d ⊙ T = {0 ≤ t ≤ d (max T + 1): d |t ⇒ t/d ∈ T} . We show that espd⊙T (G) = d espT (G) − r, where r, 0 ≤ r ≤ d − 1, is an integer that depends on T and G. Next we focus on the case T = {0} and show that espd⊙{0} (G) = ⌈d(χc(G) − 1)⌉, where χc(G) is the circular chromatic number of G. This result allows us to formulate several interesting conclusions that include a new formula for the circular chromatic number χc(G) = 1 + inf espd⊙{0} (G)/d: d ≥ 1 and a proof that the formula for the T-edge span of powers of cycles, stated as conjecture in [Y. Zhao, W. He and R. Cao, The edge span of T-coloring on graph C d n , Appl. Math. Lett. 19 (2006) 647–651], is true.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (3)
Cite as
Full text
- Publication version
- Accepted or Published Version
- License
- open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
Discussiones Mathematicae Graph Theory
no. 41,
pages 441 - 450,
ISSN: 1234-3099 - Language:
- English
- Publication year:
- 2021
- Bibliographic description:
- Janczewski R., Trzaskowska A. M., Turowski K.: T-colorings, divisibility and circular chromatic number// Discussiones Mathematicae Graph Theory -Vol. 41, (2021), s.441-450
- DOI:
- Digital Object Identifier (open in new tab) 10.7151/dmgt.2198
- Bibliography: test
-
- M.B. Cozzens and F.S. Roberts, T -colorings of graphs and the channel assigment problem, Congr. Numer. 35 (1982) 191-208. open in new tab
- K. Giaro, R. Janczewski and M. Ma lafiejski, A polynomial algorithm for finding T - span of generalized cacti , Discrete Appl. Math. 129 (2003) 371-382. doi:10.1016/S0166-218X(02)00575-9 open in new tab
- K. Giaro, R. Janczewski and M. Ma lafiejski, The complexity of the T -coloring prob- lem for graphs with small degree, Discrete Appl. Math. 129 (2003) 361-369. doi:10.1016/S0166-218X(02)00576-0 open in new tab
- G. Fan, Circular chromatic number and Mycielski graphs, Combinatorica 24 (2004) 127-135. doi:10.1007/s00493-004-0008-9 open in new tab
- W.K. Hale, Frequency assigment: theory and applications, Proc. IEEE 68 (1980) 1497-1514. doi:10.1109/PROC.1980.11899 open in new tab
- R. Janczewski, Divisibility and T -span of graphs, Discrete Math. 234 (2001) 171-179. doi:10.1016/S0012-365X(00)00378-2 open in new tab
- R. Janczewski, Greedy T -colorings of graphs, Discrete Math. 309 (2009) 1685-1690. doi:10.1016/j.disc.2008.01.049 open in new tab
- J.S.-T. Juan, I. Sun and P.-X. Wu, T -coloring on folded hypercubes, Taiwanese J. Math. 13 (2009) 1331-1341. doi:10.11650/twjm/1500405511 open in new tab
- A. Raychaudhuri, Further results on T -coloring and frequency assignment problems, SIAM J. Discrete Math. 7 (1994) 605-613. doi:10.1137/S0895480189171746 open in new tab
- D. Moser, The star-chromatic number of planar graphs, J. Graph Theory 24 (1997) 33-43. doi:10.1002/(SICI)1097-0118(199701)24:1 33::AID-JGT5 3.0.CO;2-K open in new tab
- B. Tesman, Applications of forbidden difference graphs to T -coloring, Congr. Numer. 74 (1990) 15-24.
- R. Janczewski, A.M. Trzaskowska and K. Turowski open in new tab
- A. Vince, Star chromatic number , J. Graph Theory 12 (1988) 551-559. doi:10.1002/jgt.3190120411 open in new tab
- Y. Zhao, W. He and R. Cao, The edge span of T -coloring on graph C d n , Appl. Math.
- Lett. 19 (2006) 647-651. doi:10.1016/j.aml.2005.08.016 open in new tab
- X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001) 371-410. doi:10.1016/S0012-365X(00)00217-X open in new tab
- X. Zhu, Recent developments in circular colouring of graphs, Algorithms Combin. 26 (2006) 497-550. doi:10.1007/3-540-33700-8 25 open in new tab
- Verified by:
- Gdańsk University of Technology
seen 226 times
Recommended for you
TOTAL DOMINATION MULTISUBDIVISION NUMBER OF A GRAPH
- D. Avella-alaminos,
- M. Dettlaff,
- M. Lemańska
- + 1 authors
Equitable coloring of corona products of graphs
- H. Furmańczyk,
- K. Kaliraj,
- M. Kubale
- + 1 authors