Let P and Q be additive and hereditary graph properties, r, s ∈ N, r ≥ s, and [ℤr]s be the set of all s-element subsets of ℤr. An (r, s)-fractional (P,Q)-total coloring of G is an assignment h : V (G) ∪ E(G) → [ℤr]s such that for each i ∈ ℤr the following holds: the vertices of G whose color sets contain color i induce a subgraph of G with property P, edges with color sets containing color i induce a subgraph of G with property Q, and the color sets of incident vertices and edges are disjoint. If each vertex and edge of G is colored with a set of s consecutive elements of ℤr we obtain an (r, s)-circular (P,Q)-total coloring of G. In this paper we present basic results on (r, s)-fractional/circular (P,Q)-total colorings. We introduce the fractional and circular (P,Q)-total chromatic number of a graph and we determine this number for complete graphs and some classes of additive and hereditary properties.
@article{bwmeta1.element.doi-10_7151_dmgt_1812,
author = {Arnfried Kemnitz and Massimiliano Marangio and Peter Mih\'ok and Janka Oravcov\'a and Roman Sot\'ak},
title = {Generalized Fractional and Circular Total Colorings of Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {517-532},
zbl = {1317.05060},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1812}
}
Arnfried Kemnitz; Massimiliano Marangio; Peter Mihók; Janka Oravcová; Roman Soták. Generalized Fractional and Circular Total Colorings of Graphs. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 517-532. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1812/
[1] I. Bárány, A short proof of Kneser’s Conjecture, J. Combin. Theory Ser. A 25 (1978) 325-326. doi:10.1016/0097-3165(78)90023-7[Crossref] | Zbl 0404.05028
[2] 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] | Zbl 1234.05076
[3] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, Ed., Advances in Graph Theory, Vishwa International Publications, Gulbarga (1991) 42-69.
[4] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semaniˇsin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50. doi:10.7151/dmgt.1037[Crossref] | Zbl 0902.05026
[5] F.R.K. Chung, On the Ramsey numbers N(3, 3, . . . , 3; 2), Discrete Math. 5 (1973) 317-321. doi:10.1016/0012-365X(73)90125-8 [Crossref]
[6] M.J. Dorfling and S. Dorfling, Generalized edge-chromatic numbers and additive hereditary properties of graphs, Discuss. Math. Graph Theory 22 (2002) 349-359. doi:10.7151/dmgt.1180[Crossref] | Zbl 1030.05039
[7] A. Hackmann and A. Kemnitz, Circular total colorings of graphs, Congr. Numer. 158 (2002) 43-50. | Zbl 1032.05053
[8] R.P. Jones, Hereditary properties and P-chromatic numbers, in: Combinatorics, London Math. Soc. Lecture Note, (Cambridge Univ. Press, London) 13 (1974) 83-88.[Crossref]
[9] G. Karafová, Generalized fractional total coloring of complete graphs, Discuss. Math. Graph Theory 33 (2013) 665-676. doi:10.7151/dmgt.1697[Crossref] | Zbl 06323187
[10] K. Kilakos and B. Reed, Fractionally colouring total graphs, Combinatorica 13 (1993) 435-440. doi:10.1007/BF01303515[Crossref] | Zbl 0795.05056
[11] L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. The- ory Ser. A 25 (1978) 319-324. doi:10.1016/0097-3165(78)90022-5[Crossref]
[12] P. Mihók, Zs. Tuza and M. Voigt, Fractional P-colourings and P-choice-ratio, Tatra Mt. Math. Publ. 18 (1999) 69-77. | Zbl 0951.05035
[13] E.R. Scheinerman and D.H. Ullman, Fractional Graph Theory (John Wiley & Sons, New York, 1997). http://www.ams.jhu.edu/∼ers/fgt. | Zbl 0891.05003