DMGT

Discussiones Mathematicae Graph Theory 33(4) (2013) 665-676
DOI: https://doi.org/10.7151/dmgt.1697

Generalized Fractional Total Colorings of Complete Graphs

Gabriela Karafová

Institute of Mathematics,
P.J. Šafárik University, Jesenná 5,
040 01 Košice, Slovakia

Abstract

An additive and hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let P and Q be two 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 of property P, all edges of color i induce a subgraph of property Q and vertices and incident edges have assigned disjoint sets of colors. The minimum ratio r/s of an (r/s)-fractional (P,Q)-total coloring of G is called fractional (P,Q)-total chromatic number χ ′ ′_f,P,Q(G) = r/s. Let k = sup{i:K_i+1 ∈ P} and l = sup{i:K_i+1 ∈ Q}. We show for a complete graph K_n that if l ≥ k+2 then χ ′ ′_f,P,Q(K_n) = n/(k+1) for a sufficiently large n.

Keywords: fractional coloring, total coloring, complete graphs

2010 Mathematics Subject Classification: 05C15.

References

[1]	M. Behzad, Graphs and their chromatic numbers, Doctoral Thesis (Michigan state University, 1965).
[2]	M. Behzad, The total chromatic number of a graph, in: Combinatorial Mathematics and its Applications, D.J.A.Welsh, Ed., (Academic Press, London, 1971) 1--10.
[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.
[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.
[5]	M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: Advances in Graph Theory, V.R. Kulli, Ed., (Vishwa International Publication, Gulbarga, 1991) 41--68.
[6]	A. Chetwynd, Total colourings, in: Graphs Colourings, Pitman Research Notes in Mathematics No.218, R. Nelson and R.J. Wilson Eds., (London, 1990) 65--77.
[7]	A. Kemnitz, M. Marangio, P. Mihók, J. Oravcová and R. Soták, Generalized fractional and circular total colorings of graphs, (2010), preprint.
[8]	K. Kilakos and B. Reed, Fractionally colouring total graphs, Combinatorica 13 (1993) 435--440, doi: 10.1007/BF01303515.
[9]	V.G. Vizing, Some unsolved problems in graph theory, Russian Math. Surveys 23 (1968) 125--141, doi: 10.1070/RM1968v023n06ABEH001252.