Fractional (\( \mathcal{P} , \mathcal{Q} \))-Total List Colorings of Graphs

Kemnitz, Arnfried ; Mihók, Peter ; Voigt, Margit

Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 167-179

Résumé

Let r, s ∈ℕ, r ≥ s, and 𝒫 and 𝒬 be two additive and hereditary graph properties. A (P,Q)-total (r, s)-coloring of a graph G = (V,E) is a coloring of the vertices and edges of G by s-element subsets of ℤ_r such that for each color i, 0 ≤ i ≤ r − 1, the vertices colored by subsets containing i induce a subgraph of G with property 𝒫, the edges colored by subsets containing i induce a subgraph of G with property 𝒬, and color sets of incident vertices and edges are disjoint. The fractional (𝒫, 𝒬)-total chromatic number χ_f,P,Q^”(G) of G is defined as the infimum of all ratios r//s such that G has a ( 𝒫, 𝒬)-total (r, s)-coloring. A ( 𝒫, 𝒬-total independent set T = V_T ∪ E_T ⊆ V ∪ E is the union of a set V_T of vertices and a set E_T of edges of G such that for the graphs induced by the sets V_T and E_T it holds that G[ V_T ] ∈ 𝒫, G[ E_T ] ∈𝒬, and G[ V_T ] and G[ E_T ] are disjoint. Let T_𝒫 , 𝒬 be the set of all (𝒫 ,𝒬)-total independent sets of G. Let L(x) be a set of admissible colors for every element x ∈ V ∪ E. The graph G is called (𝒫 , 𝒬)-total (a, b)-list colorable if for each list assignment L with |L(x)| = a for all x ∈ V ∪ E it is possible to choose a subset C(x) ⊆ L(x) with |C(x)| = b for all x ∈ V ∪ E such that the set T_i which is defined by T_i = x ∈ V ∪ E : i ∈ C(x) belongs to T_𝒫,𝒬 for every color i. The (𝒫, 𝒬)- choice ratio chr_𝒫,𝒬(G) of G is defined as the infimum of all ratios a//b such that G is (𝒫,𝒬)-total (a, b)-list colorable. We give a direct proof of χ_ f,𝒫,𝒬^'' (G) = chr_𝒫 ,𝒬(G) for all simple graphs G and we present for some properties 𝒫 and 𝒬 new bounds for the (𝒫, 𝒬)-total chromatic number and for the (𝒫,𝒬)-choice ratio of a graph G.

Détail

Keywords: graph property, total coloring, (P,Q)-total coloring, fractional coloring, fractional (P,Q)-total chromatic number, circular coloring, circular (P,Q)-total chromatic number, list coloring, (P,Q)-total (a, b)-list colorings