Decompositions of Plane Graphs Under Parity Constrains Given by Faces

Július Czap; Zsolt Tuza

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 3, page 521-530
  • ISSN: 2083-5892

Abstract

top
An edge coloring of a plane graph G is facially proper if no two faceadjacent 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?

How to cite

top

Július Czap, and Zsolt Tuza. "Decompositions of Plane Graphs Under Parity Constrains Given by Faces." Discussiones Mathematicae Graph Theory 33.3 (2013): 521-530. <http://eudml.org/doc/268185>.

@article{JúliusCzap2013,
abstract = {An edge coloring of a plane graph G is facially proper if no two faceadjacent 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?},
author = {Július Czap, Zsolt Tuza},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {plane graph; parity partition; edge coloring; facial parity edge coloringfacial; facially proper parity edge coloring},
language = {eng},
number = {3},
pages = {521-530},
title = {Decompositions of Plane Graphs Under Parity Constrains Given by Faces},
url = {http://eudml.org/doc/268185},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Július Czap
AU - Zsolt Tuza
TI - Decompositions of Plane Graphs Under Parity Constrains Given by Faces
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 3
SP - 521
EP - 530
AB - An edge coloring of a plane graph G is facially proper if no two faceadjacent 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?
LA - eng
KW - plane graph; parity partition; edge coloring; facial parity edge coloringfacial; facially proper parity edge coloring
UR - http://eudml.org/doc/268185
ER -

References

top
  1. [1] J. Czap, S. Jendroľ, F. Kardoš and R. Sotak, Facial parity edge coloring of plane pseudographs, Discrete Math. 312 (2012) 2735-2740. doi:10.1016/j.disc.2012.03.036[Crossref][WoS] Zbl1245.05044
  2. [2] J. Czap and Zs. Tuza, Partitions of graphs and set systems under parity constraints, preprint (2011). 
  3. [3] D. Gon，calves, 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[Crossref] 
  4. [4] S. Grunewald, Chromatic index critical graphs and multigraphs, PhD Thesis, Universitat Bielefeld (2000). Zbl0947.05030
  5. [5] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. Cas. SAV (Math. Slovaca) 5 (1955) 101-113 (in Slovak). 
  6. [6] T. Matrai, Covering the edges of a graph by three odd subgraphs, J. Graph Theory 53 (2006) 75-82. doi:10.1002/jgt.20170[Crossref] Zbl1098.05067
  7. [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[Crossref] Zbl0119.38805
  8. [8] L. Pyber, Covering the edges of a graph by . . . , Colloquia Mathematica Societatis Janos Bolyai, 60. Sets, Graphs and Numbers (1991) 583-610. Zbl0792.05110
  9. [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[Crossref] Zbl1024.05031
  10. [10] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz 3 (1964) 25-30. 
  11. [11] L. Zhang, Every planar graph with maximum degree 7 is class I, Graphs Combin. 16 (2000) 467-495. doi:10.1007/s003730070009 [Crossref] Zbl0988.05042

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.