PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 35 | 3 | 463-473
Tytuł artykułu

Generalized Fractional Total Colorings of Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Let P and Q be additive and hereditary graph properties and let r, s be integers such that r ≥ s. Then an r/s -fractional (P,Q)-total coloring of a finite graph G = (V,E) is a mapping f, which assigns an s-element subset of the set {1, 2, . . . , r} to each vertex and each edge, moreover, for any color i all vertices of color i induce a subgraph with property P, all edges of color i induce a subgraph with property Q and vertices and incident edges have been assigned disjoint sets of colors. The minimum ratio of an r/s -fractional (P,Q)-total coloring of G is called fractional (P,Q)-total chromatic number χ″ƒ,P,Q(G) = r/ s . We show in this paper that χ″ƒ,P,Q of a graph G with o(V (G)) vertex orbits and o(E(G)) edge orbits can be found as a solution of a linear program with integer coefficients which consists only of o(V (G)) + o(E(G)) inequalities.
Wydawca
Rocznik
Tom
35
Numer
3
Strony
463-473
Opis fizyczny
Daty
wydano
2015-08-01
otrzymano
2014-04-03
poprawiono
2014-09-03
zaakceptowano
2014-09-03
online
2015-07-29
Twórcy
autor
  • Institute of Mathematics, P. J. Šafárik University, Jesenná 5, 040 01 Košice, Slovakia, roman.sotak@upjs.sk
Bibliografia
  • [1] M. Behzad, Graphs and their chromatic numbers, Ph.D. Thesis, (Michigan State University, 1965).
  • [2] M. Behzad, The total chromatic number of a graph, a survey, in: Proc. Conf. Oxford, 1969, Combinatorial Mathematics and its Applications, (Academic Press, London, 1971) 1-8.
  • [3] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50. doi:10.7151/dmgt.1037[Crossref]
  • [4] M. Borowiecki, A. Kemnitz, M. Marangio and P. Mihók, Generalized total colorings of graphs, Discuss. Math. Graph Theory 31(2011) 209-222. doi:10.7151/dmgt.1540[WoS][Crossref]
  • [5] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli (Ed.), Advances in Graph Theory (Vishwa International Publication, Gulbarga, 1991) 41-68.
  • [6] A.G. Chetwynd, Total colourings, in: Graphs Colourings, R. Nelson and R.J.Wilson (Eds.), Pitman Research Notes in Mathematics 218 (London, 1990) 65-77.
  • [7] J.L. Gross and J. Yellen, Graph Theory and Its Applications, (CRC Press, New York 2006) 58-72.
  • [8] G. Karafová, Generalized fractional total coloring of complete graphs, Discuss. Math. Graph Theory 33 (2013) 665-676. doi:10.7151/dmgt.1697[Crossref]
  • [9] A. Kemnitz, M. Marangio, P. Mihók, J. Oravcová and R. Soták, Generalized fractional and circular total colorings of graphs, (2010), preprint.
  • [10] K. Kilakos and B. Reed, Fractionally colouring total graphs, Combinatorica 13 (1993) 435-440. doi:10.1007/BF01303515[Crossref]
  • [11] E.R. Scheinerman and D.H. Ullman, Fractional Graph Theory (John Wiley and Sons, New York, 1997).
  • [12] V.G. Vizing, Some unsolved problems in graph theory, Russian Math. Surveys 23 (1968) 125-141. doi:10.1070/RM1968v023n06ABEH001252 [Crossref]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1810
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.