Wyniki wyszukiwania

1

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

100%

Kemnitz A., Mihók P., Voigt M.

Discussiones Mathematicae Graph Theory

|

2013

|

tom 33

|

nr 1

167-179

EN

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.

2

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Preface

100%

Harant J., Voigt M., Schiermeyer I.

Discussiones Mathematicae Graph Theory

|

2002

|

tom 22

|

nr 1

5-6

3

Sum List Edge Colorings of Graphs

100%

Kemnitz A., Marangio M., Voigt M.

Discussiones Mathematicae Graph Theory

|

2016

|

tom 36

|

nr 3

709-722

EN

Let G = (V,E) be a simple graph and for every edge e ∈ E let L(e) be a set (list) of available colors. The graph G is called L-edge colorable if there is a proper edge coloring c of G with c(e) ∈ L(e) for all e ∈ E. A function f : E → ℕ is called an edge choice function of G and G is said to be f-edge choosable if G is L-edge colorable for every list assignment L with |L(e)| = f(e) for all e ∈ E. Set size(f) = ∑e∈E f(e) and define the sum choice index χ′sc(G) as the minimum of size(f) over all edge choice functions f of G. There exists a greedy coloring of the edges of G which leads to the upper bound χ′sc(G) ≤ 1/2 ∑v∈V d(v)2. A graph is called sec-greedy if its sum choice index equals this upper bound. We present some general results on the sum choice index of graphs including a lower bound and we determine this index for several classes of graphs. Moreover, we present classes of sec-greedy graphs as well as all such graphs of order at most 5.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

3 Voigt M.

2 Kemnitz A.

1 Harant J.

1 Marangio M.

1 Mihók P.

1 Schiermeyer I.

1 2016

1 2013

1 2002

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

Preface

Sum List Edge Colorings of Graphs