T-colorings, divisibility and circular chromatic number - Publikacja - MOST Wiedzy

Wyszukiwarka

T-colorings, divisibility and circular chromatic number

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

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
Discussiones Mathematicae Graph Theory strony 1 - 10,
ISSN: 1234-3099
Rok wydania:
2019
Opis bibliograficzny:
Janczewski R., Trzaskowska A. M., Turowski K.: T-colorings, divisibility and circular chromatic number// Discussiones Mathematicae Graph Theory. -, (2019), s.1-10
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.2198
Bibliografia: test
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  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 otwiera się w nowej karcie
  9. 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
  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 otwiera się w nowej karcie
  11. B. Tesman, Applications of forbidden difference graphs to T -coloring, Congr. Numer. 74 (1990) 15-24.
  12. R. Janczewski, A.M. Trzaskowska and K. Turowski otwiera się w nowej karcie
  13. A. Vince, Star chromatic number , J. Graph Theory 12 (1988) 551-559. doi:10.1002/jgt.3190120411 otwiera się w nowej karcie
  14. Y. Zhao, W. He and R. Cao, The edge span of T -coloring on graph C d n , Appl. Math.
  15. Lett. 19 (2006) 647-651. doi:10.1016/j.aml.2005.08.016 otwiera się w nowej karcie
  16. 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
  17. 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 50 razy

Publikacje, które mogą cię zainteresować

Meta Tagi