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

Arnfried Kemnitz; Peter Mihók; Margit Voigt

Discussiones Mathematicae Graph Theory (2013)

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

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.