Discussiones Mathematicae Graph Theory 33(3) (2013) 509-519
doi: 10.7151/dmgt.1685

[BIBTex] [PDF] [PS]

Fractional Q-edge-coloring of Graphs

Július Czap

Department of Applied Mathematics and Business Informatics
Faculty of Economics, Technical University of Košice
Němcovej 32, SK-040 01 Košice, Slovakia

Peter Mihók

Department of Applied Mathematics and Business Informatics
Faculty of Economics, Technical University of Košice
Němcovej 32, SK-040 01 Košice, Slovakia
and
Mathematical Institute of the Slovak Academy of Sciences
Grešákova 6, SK-040 01 Košice, Slovakia

Abstract

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let Q be an additive hereditary property of graphs. A Q-edge-coloring of a simple graph is an edge coloring in which the edges colored with the same color induce a subgraph of property Q. In this paper we present some results on fractional Q-edge-colorings. We determine the fractional Q-edge chromatic number for matroidal properties of graphs.

Keywords: fractional coloring, graph property

2010 Mathematics Subject Classification: 05C15, 05C70, 05C72.

References

[1]J.A. Bondy and U.S.R. Murty, Graph Theory ( Springer, 2008)..
[2]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.
[3]I. Broere, S. Dorfling and E. Jonck, Generalized chromatic numbers and additive hereditary properties of graphs, Discuss. Math. Graph Theory 22 (2002) 259--270, doi: 10.7151/dmgt.1174.
[4]M.J. Dorfling and S. Dorfling, Generalized edge-chromatic numbers and additive hereditary properties of graphs, Discuss. Math. Graph Theory 22 (2002) 349--359, doi: 10.7151/dmgt.1180.
[5]J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices, J. Res. Nat. Bur. Standards 69B (1965) 125--130..
[6]G. Karafová, Generalized fractional total coloring of complete graphs, Discuss. Math. Graph Theory, accepted..
[7]A. Kemnitz, M. Marangio, P. Mihók, J. Oravcová and R. Soták, Generalized fractional and circular total coloring of graphs, preprint..
[8]K. Kilakos and B. Reed, Fractionally colouring total graphs, Combinatorica 13 (1993) 435--440, doi: 10.1007/BF01303515.
[9]P. Mihók, On graphs matroidal with respect to additive hereditary properties, Graphs, Hypergraphs and Matroids II, Zielona Góra (1987) 53--64..
[10]P. Mihók, Zs. Tuza and M. Voigt, Fractional P-colourings and P-choice-ratio, Tatra Mt. Math. Publ. 18 (1999) 69--77..
[11]J.G. Oxley, Matroid Theory (Oxford University Press, Oxford, 1992)..
[12]E.R. Scheinerman and D.H. Ullman, Fractional Graph Theory (John Wiley & Sons , 1997)..
[13]R. Schmidt, On the existence of uncountably many matroidal families, Discrete Math. 27 (1979) 93--97, doi: 10.1016/0012-365X(79)90072-4.
[14]J.M.S. Simões-Pereira, On matroids on edge sets of graphs with connected subgraphs as circuits, Proc. Amer. Math. Soc. 38 (1973) 503--506, doi: 10.2307/2038939.

Received 3 November 2011
Revised 29 May 2012
Accepted 29 May 2012