Fractional (P,Q)-Total List Colorings of Graphs

Arnfried Kemnitz, Peter Mihók, and Margit Voigt. "Fractional (P,Q)-Total List Colorings of Graphs." Discussiones Mathematicae Graph Theory 33.1 (2013): 167-179. <http://eudml.org/doc/267990>.

@article{ArnfriedKemnitz2013,
abstract = {Let r, s ∈ N, r ≥ s, and P and Q 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 Zr such that for each color i, 0 ≤ i ≤ r − 1, the vertices colored by subsets containing i induce a subgraph of G with property P, the edges colored by subsets containing i induce a subgraph of G with property Q, and color sets of incident vertices and edges are disjoint. The fractional (P,Q)-total chromatic number χ′′ f,P,Q(G) of G is defined as the infimum of all ratios r/s such that G has a (P,Q)-total (r, s)-coloring. A (P,Q)-total independent set T = VT ∪ET ⊆ V ∪E is the union of a set VT of vertices and a set ET of edges of G such that for the graphs induced by the sets VT and ET it holds that G[VT ] ∈ P, G[ET ] ∈ Q, and G[VT ] and G[ET ] are disjoint. Let TP,Q be the set of all (P,Q)-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 (P,Q)-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 Ti which is defined by Ti = \{x ∈ V ∪ E : i ∈ C(x)\} belongs to TP,Q for every color i. The (P,Q)- choice ratio chrP,Q(G) of G is defined as the infimum of all ratios a/b such that G is (P,Q)-total (a, b)-list colorable. We give a direct proof of χ′′ f,P,Q(G) = chrP,Q(G) for all simple graphs G and we present for some properties P and Q new bounds for the (P,Q)-total chromatic number and for the (P,Q)-choice ratio of a graph G.},
author = {Arnfried Kemnitz, Peter Mihók, Margit Voigt},
journal = {Discussiones Mathematicae Graph Theory},
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; ()-total coloring; fractional ()-total chromatic number; circular ()-total chromatic number; ()-total ()-list colorings},
language = {eng},
number = {1},
pages = {167-179},
title = {Fractional (P,Q)-Total List Colorings of Graphs},
url = {http://eudml.org/doc/267990},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Arnfried Kemnitz
AU - Peter Mihók
AU - Margit Voigt
TI - Fractional (P,Q)-Total List Colorings of Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 1
SP - 167
EP - 179
AB - Let r, s ∈ N, r ≥ s, and P and Q 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 Zr such that for each color i, 0 ≤ i ≤ r − 1, the vertices colored by subsets containing i induce a subgraph of G with property P, the edges colored by subsets containing i induce a subgraph of G with property Q, and color sets of incident vertices and edges are disjoint. The fractional (P,Q)-total chromatic number χ′′ f,P,Q(G) of G is defined as the infimum of all ratios r/s such that G has a (P,Q)-total (r, s)-coloring. A (P,Q)-total independent set T = VT ∪ET ⊆ V ∪E is the union of a set VT of vertices and a set ET of edges of G such that for the graphs induced by the sets VT and ET it holds that G[VT ] ∈ P, G[ET ] ∈ Q, and G[VT ] and G[ET ] are disjoint. Let TP,Q be the set of all (P,Q)-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 (P,Q)-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 Ti which is defined by Ti = {x ∈ V ∪ E : i ∈ C(x)} belongs to TP,Q for every color i. The (P,Q)- choice ratio chrP,Q(G) of G is defined as the infimum of all ratios a/b such that G is (P,Q)-total (a, b)-list colorable. We give a direct proof of χ′′ f,P,Q(G) = chrP,Q(G) for all simple graphs G and we present for some properties P and Q new bounds for the (P,Q)-total chromatic number and for the (P,Q)-choice ratio of a graph G.
LA - eng
KW - 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; ()-total coloring; fractional ()-total chromatic number; circular ()-total chromatic number; ()-total ()-list colorings
UR - http://eudml.org/doc/267990
ER -