DMGT

Discussiones Mathematicae Graph Theory 33(3) (2013) 521-530
DOI: https://doi.org/10.7151/dmgt.1690

Decompositions of Plane Graphs under Parity Constrains Given by Faces

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

Zsolt Tuza

Alfréd Rényi Institute of Mathematics
Hungarian Academy of Sciences
H-1053 Budapest, Reáltanoda u.~13--15, Hungary
and
Department of Computer Science and Systems Technology
University of Pannonia
H-8200 Veszprém, Egyetem u.~10, Hungary
e-mail: tuza@dcs.uni-pannon.hu

Abstract

An edge coloring of a plane graph G is facially proper if no two face-adjacent edges of G receive the same color. A facial (facially proper) parity edge coloring of a plane graph G is an (facially proper) edge coloring with the property that, for each color c and each face f of G, either an odd number of edges incident with f is colored with c, or color c does not occur on the edges of f. In this paper we deal with the following question: For which integers k does there exist a facial (facially proper) parity edge coloring of a plane graph G with exactly k colors?

Keywords: plane graph, parity partition, edge coloring

2010 Mathematics Subject Classification: 05C10, 05C15.

References

[1]	J. Czap, S. Jendrol', F. Kardoš and R. Soták, Facial parity edge coloring of plane pseudographs, Discrete Math. 312 (2012) 2735--2740, doi: 10.1016/j.disc.2012.03.036.
[2]	J. Czap and Zs. Tuza, Partitions of graphs and set systems under parity constraints, preprint (2011).
[3]	D. Gonçalves, Edge partition of planar graphs into two outerplanar graphs, Proceedings of the 37th Annual ACM Symposium on Theory of Computing (2005) 504--512, doi: 10.1145/1060590.1060666.
[4]	S. Grünewald, {Chromatic index critical graphs and multigraphs}, PhD Thesis, Universität Bielefeld (2000).
[5]	A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. Cas. SAV (Math. Slovaca) 5 (1955) 101--113 (in Slovak).
[6]	T. Mátrai, Covering the edges of a graph by three odd subgraphs, J. Graph Theory 53 (2006) 75--82, doi: 10.1002/jgt.20170.
[7]	C.St.J.A. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964) 12--12, doi: 10.1112/jlms/s1-39.1.12.
[8]	L. Pyber, Covering the edges of a graph by ..., Colloquia Mathematica Societatis János Bolyai, 60. Sets, Graphs and Numbers (1991) 583--610.
[9]	D.P. Sanders and Y. Zhao, Planar graphs of maximum degree seven are class I, J. Combin. Theory (B) 83 (2001) 201--212, doi: 10.1006/jctb.2001.2047.
[10]	V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz 3 (1964) 25--30.
[11]	L. Zhang, Every planar graph with maximum degree 7 is class I, Graphs Combin. 16 (2000) 467--495, doi: 10.1007/s003730070009.

Received 19 October 2011
Revised 11 January 2013
Accepted 14 January 2013