Generalized Fractional and Circular Total Colorings of Graphs

• Autorzy: Arnfried Kemnitz , Massimiliano Marangio , Peter Mihók , Janka Oravcová , Roman Soták
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph property; (P,Q)-total coloring; circular coloring; fractional coloring; fractional (P,Q)-total chromatic number; circular (P,Q)- total chromatic number.

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 3
• Strony: 517-532

Daty

wydano

2015-08-01

otrzymano

2014-05-08

poprawiono

2014-10-24

zaakceptowano

2014-10-24

online

2015-07-29

Twórcy

autor

Arnfried Kemnitz

• Computational Mathematics Technical University Braunschweig, Germany

autor

Massimiliano Marangio

• Computational Mathematics Technical University Braunschweig, Germany

autor

Peter Mihók

• Mathematical Institute, Slovak Academy of Sciences Grešákova 6, 040 01 Košice, Slovak Republic
• Department of Applied Mathematics and Business Informatics Faculty of Economics, Technical University B.Nĕmcovej 32, 040 01 Košice, Slovak Republic

autor

Janka Oravcová

• Department of Applied Mathematics and Business Informatics Faculty of Economics, Technical University B.Nĕmcovej 32, 040 01 Košice, Slovak Republic

autor

Roman Soták

• Institute of Mathematics Faculty of Science, P.J. Šafárik University Jesenná 5, 041 54 Košice, Slovak Republic

Bibliografia

• [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]
• [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]
• [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]
• [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]
• [7] A. Hackmann and A. Kemnitz, Circular total colorings of graphs, Congr. Numer. 158 (2002) 43-50.
• [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]
• [10] K. Kilakos and B. Reed, Fractionally colouring total graphs, Combinatorica 13 (1993) 435-440. doi:10.1007/BF01303515[Crossref]
• [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.
• [13] E.R. Scheinerman and D.H. Ullman, Fractional Graph Theory (John Wiley & Sons, New York, 1997). http://www.ams.jhu.edu/∼ers/fgt.

Identyfikatory

DOI

10.7151/dmgt.1812