Geodesic
T-Colorings, Divisibility and the Circular Chromatic Number
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 441-450.

Voir la notice de l'article provenant de la source Library of Science

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 esp_T(G) and esp_d⊙T(G), where d is a positive integer and d⊙T={ 0≤t≤d(maxT+1):d|t⇒t/d∈T}. We show that esp_d⊙T(G) = d esp_T(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 esp_d⊙{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{esp_d⊙{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_n^d, Appl. Math. Lett. 19 (2006) 647–651], is true.
Keywords: circular chromatic number, T-coloring 
@article{DMGT_2021_41_2_a6,
     author = {Janczewski, Robert and Trzaskowska, Anna Maria and Turowski, Krzysztof},
     title = {T-Colorings, {Divisibility} and the {Circular} {Chromatic} {Number}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {441--450},
     publisher = {mathdoc},
     volume = {41},
     number = {2},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a6/}
}
TY  - JOUR
AU  - Janczewski, Robert
AU  - Trzaskowska, Anna Maria
AU  - Turowski, Krzysztof
TI  - T-Colorings, Divisibility and the Circular Chromatic Number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 441
EP  - 450
VL  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a6/
LA  - en
ID  - DMGT_2021_41_2_a6
ER  - 
%0 Journal Article
%A Janczewski, Robert
%A Trzaskowska, Anna Maria
%A Turowski, Krzysztof
%T T-Colorings, Divisibility and the Circular Chromatic Number
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 441-450
%V 41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a6/
%G en
%F DMGT_2021_41_2_a6
Janczewski, Robert; Trzaskowska, Anna Maria; Turowski, Krzysztof. T-Colorings, Divisibility and the Circular Chromatic Number. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 441-450. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a6/

[1] M.B. Cozzens and F.S. Roberts, T-colorings of graphs and the channel assigment problem, Congr. Numer. 35 (1982) 191–208.

[2] K. Giaro, R. Janczewski and M. Małafiejski, 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

[3] K. Giaro, R. Janczewski and M. Małafiejski, The complexity of the T-coloring problem for graphs with small degree, Discrete Appl. Math. 129 (2003) 361–369. doi:10.1016/S0166-218X(02)00576-0

[4] G. Fan, Circular chromatic number and Mycielski graphs, Combinatorica 24 (2004) 127–135. doi:10.1007/s00493-004-0008-9

[5] W.K. Hale, Frequency assigment: theory and applications, Proc. IEEE 68 (1980) 1497–1514. doi:10.1109/PROC.1980.11899

[6] R. Janczewski, Divisibility and T-span of graphs, Discrete Math. 234 (2001) 171–179. doi:10.1016/S0012-365X(00)00378-2

[7] R. Janczewski, Greedy T-colorings of graphs, Discrete Math. 309 (2009) 1685–1690. doi:10.1016/j.disc.2008.01.049

[8] 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

[9] A. Raychaudhuri, Further results on T-coloring and frequency assignment problems, SIAM J. Discrete Math. 7 (1994) 605–613. doi:10.1137/S0895480189171746

[10] 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

[11] B. Tesman, Applications of forbidden difference graphs to T-coloring, Congr. Numer. 74 (1990) 15–24.

[12] A. Vince, Star chromatic number, J. Graph Theory 12 (1988) 551–559. doi:10.1002/jgt.3190120411

[13] Y. Zhao, W. He and R. Cao, The edge span of T-coloring on graph $C_n^d$, Appl. Math. Lett. 19 (2006) 647–651. doi:10.1016/j.aml.2005.08.016

[14] X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001) 371–410. doi:10.1016/S0012-365X(00)00217-X

[15] X. Zhu, Recent developments in circular colouring of graphs, Algorithms Combin. 26 (2006) 497–550. doi:10.1007/3-540-33700-8_25