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

• Volume: 33, Issue: 1, page 167-179
• ISSN: 2083-5892

top

## Abstract

top
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.

## How to cite

top

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 -

## References

top
1. [1] N. Alon and K.A. Berman, Regular hypergraphs, Gordon’s Lemma, Steinitz’ Lemma and invariant theory, J. Combin. Theory (A) 43 (1986) 91-97. doi:10.1016/0097-3165(86)90026-9[Crossref] Zbl0611.05044
2. [2] N. Alon, Zs. Tuza, and M. Voigt, Choosability and fractional chromatic number, Discrete Math. 165/166 (1997) 31-38. doi:10.1016/S0012-365X(96)00159-8[Crossref]
3. [3] I. Bárány, A vector-sum theorem and its application to improving flow shop guarantees, Math. Oper. Res. 6 (1981) 445-452. doi:10.1287/moor.6.3.445[Crossref]
4. [4] M. Behzad, Graphs and their chromatic numbers (PhD Thesis, Michigan State University, 1965).
5. [5] O.V. Borodin, On the total colouring of planar graphs, J. Reine Angew. Math. 394 (1989) 180-185. Zbl0653.05029
6. [6] M. Borowiecki, I. Broere, M. Frick, P. Mihók, and G. Semanišin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50. doi:10.7151/dmgt.1037[Crossref] Zbl0902.05026
7. [7] 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[Crossref] Zbl1234.05076
8. [8] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, (Ed.), Advances in Graph Theory, Vishwa International Publications, Gulbarga, (1991) 42-69.
9. [9] A.J.W. Hilton and H.R. Hind, Total chromatic number of graphs having large maximum degree, Discrete Math. 117 (1993) 127-140. doi:10.1016/0012-365X(93)90329-R[Crossref] Zbl0785.05035
10. [10] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley-Interscience, New York, NY, 1995).
11. [11] A. Kemnitz, M. Marangio, P. Mihók, J. Oravcová, and R. Soták, Generalized fractional and circular total colorings of graphs, preprint. Zbl1317.05060
12. [12] K. Kilakos and B. Reed, Fractionally colouring total graphs, Combinatorica 13 (1993) 435-440. doi:10.1007/BF01303515[Crossref] Zbl0795.05056
13. [13] A.V. Kostochka, The total chromatic number of any multigraph with maximum degree five is at most seven, Discrete Math. 162 (1996) 199-214. doi:10.1016/0012-365X(95)00286-6[Crossref] Zbl0871.05023
14. [14] P. Mihók, Zs. Tuza, and M. Voigt, Fractional P-colourings and P-choice-ratio, Tatra Mt. Math. Publ. 18 (1999) 69-77. Zbl0951.05035
15. [15] M. Molloy and B. Reed, A bound on the total chromatic number, Combinatorica 18 (1998) 241-280. doi:10.1007/PL00009820[Crossref] Zbl0921.05033
16. [16] M. Molloy and B. Reed, Graph colouring and the probabilistic method, Algorithms Combin. 23 (Springer, New York, NY, 2002). Zbl0987.05002
17. [17] D.P. Sanders and Y. Zhao, On total 9-coloring planar graphs of maximum degree seven, J. Graph Theory 31 (1999) 67-73. doi:10.1002/(SICI)1097-0118(199905)31:1h67::AID-JGT6i3.0.CO;2-C[Crossref] Zbl0922.05025
18. [18] E.R. Scheinerman and D.H. Ullman, Fractional Graph Theory (John Wiley & Sons, New York, 1997) http://www.ams.jhu.edu/∼ers/fgt. Zbl0891.05003
19. [19] S.V. Sevastyanov, On approximate solutions of scheduling problems, Metody Diskr. Analiza 32 (1978) 66-75 (in Russian). Zbl0452.90033
20. [20] Zs. Tuza, M. Voigt, On a conjecture of Erd˝os, Rubin and Taylor, Tatra Mt. Math. Publ. 9 (1996) 69-82.
21. [21] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30 (in Russian).
22. [22] H.P. Yap, Total Colourings of Graphs (Lecture Notes in Mathematics 1623, Springer, Berlin, 1996). Zbl0839.05001

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.