Abstrakt
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.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Autorzy (3)
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- Licencja
- otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
Discussiones Mathematicae Graph Theory
nr 41,
strony 441 - 450,
ISSN: 1234-3099 - Język:
- angielski
- Rok wydania:
- 2021
- Opis bibliograficzny:
- 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:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.2198
- Bibliografia: test
-
- M.B. Cozzens and F.S. Roberts, T -colorings of graphs and the channel assigment problem, Congr. Numer. 35 (1982) 191-208. otwiera się w nowej karcie
- 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 otwiera się w nowej karcie
- 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 otwiera się w nowej karcie
- G. Fan, Circular chromatic number and Mycielski graphs, Combinatorica 24 (2004) 127-135. doi:10.1007/s00493-004-0008-9 otwiera się w nowej karcie
- W.K. Hale, Frequency assigment: theory and applications, Proc. IEEE 68 (1980) 1497-1514. doi:10.1109/PROC.1980.11899 otwiera się w nowej karcie
- R. Janczewski, Divisibility and T -span of graphs, Discrete Math. 234 (2001) 171-179. doi:10.1016/S0012-365X(00)00378-2 otwiera się w nowej karcie
- R. Janczewski, Greedy T -colorings of graphs, Discrete Math. 309 (2009) 1685-1690. doi:10.1016/j.disc.2008.01.049 otwiera się w nowej karcie
- 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 otwiera się w nowej karcie
- A. Raychaudhuri, Further results on T -coloring and frequency assignment problems, SIAM J. Discrete Math. 7 (1994) 605-613. doi:10.1137/S0895480189171746 otwiera się w nowej karcie
- 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 otwiera się w nowej karcie
- B. Tesman, Applications of forbidden difference graphs to T -coloring, Congr. Numer. 74 (1990) 15-24.
- R. Janczewski, A.M. Trzaskowska and K. Turowski otwiera się w nowej karcie
- A. Vince, Star chromatic number , J. Graph Theory 12 (1988) 551-559. doi:10.1002/jgt.3190120411 otwiera się w nowej karcie
- 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 otwiera się w nowej karcie
- X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001) 371-410. doi:10.1016/S0012-365X(00)00217-X otwiera się w nowej karcie
- X. Zhu, Recent developments in circular colouring of graphs, Algorithms Combin. 26 (2006) 497-550. doi:10.1007/3-540-33700-8 25 otwiera się w nowej karcie
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 216 razy
Publikacje, które mogą cię zainteresować
TOTAL DOMINATION MULTISUBDIVISION NUMBER OF A GRAPH
- D. Avella-alaminos,
- M. Dettlaff,
- M. Lemańska
- + 1 autorów
Equitable coloring of corona products of graphs
- H. Furmańczyk,
- K. Kaliraj,
- M. Kubale
- + 1 autorów