Generalized Fractional Total Colorings of Complete Graph

Karafová, Gabriela 

Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 665-676

Résumé

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.

Détail

Keywords: fractional coloring, total coloring, complete graphs