ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


R. Janczewski, A.M. Trzaskowska , K. Turowski


$T$-colorings, divisibility and circular chromatic number


Discussiones Mathematicae Graph Theory

Received: 2018-03-19, Revised: 2018-10-16, Accepted: 2018-12-07,


Let $T$ be a $T$-set, i.e., a finite set of nonnegative integers satisfying $0\in T$, and $G$ be a graph. In the paper we study relations between the $T$-edge spans $\mathrm{esp}_T(G)$ and $\mathrm{esp}_{d\odot T}(G)$, where $d$ is a positive integer and $$ d\odot T=\left\{0\leq t\leq d\,(\max\, T+1)\colon d\;|\,t\Rightarrow t/d\in T\right\}. $$ We show that $\mathrm{esp}_{d\odot T}(G)=d\mathrm{esp}_T(G)-r$, where {$r$,} $0\leq r\leq d-1$, is an integer that depends on $T$ and $G$. Next we focus on the case $T=\{0\}$ and show that $$ \mathrm{esp}_{d\odot\{0\}}(G)=\lceil d(\chi_c(G)-1)\rceil, $$ where $\chi_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 $$ \chi_c(G)=1+\inf\big\{\mathrm{esp}_{d\odot\{0\}}(G)/d\colon d\geq 1\big\} $$ 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.


$T$-coloring, circular chromatic number