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

[BIBTex] [PDF] [PS]

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:Ki+1P} and l = sup{i:Ki+1Q}. We show for a complete graph Kn that if l ≥ k+2 then χ ′ ′f,P,Q(Kn) = 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.