IJPAM: Volume 85, No. 1 (2013)
FACIAL R-ACYCLIC EDGE-COLORINGS OF PLANE GRAPHS
Kristína Budajová1, Július Czap2
1Department of Aerodynamics and Simulations
Faculty of Aeronautics
Technical University of Košice
Rampová 7, SK-041 21 Košice, SLOVAKIA
2Department of Applied Mathematics and Business Informatics
Faculty of Economics
Technical University of Košice
B. Němcovej 32, SK-040 01 Košice, SLOVAKIA
1Department of Aerodynamics and Simulations
Faculty of Aeronautics
Technical University of Košice
Rampová 7, SK-041 21 Košice, SLOVAKIA
2Department of Applied Mathematics and Business Informatics
Faculty of Economics
Technical University of Košice
B. Němcovej 32, SK-040 01 Košice, SLOVAKIA
Abstract. An edge-coloring of a 2-connected plane graph G is a r-acyclic edge-coloring if every facial cycle C in G is colored with at least min{|C|,r} colors, in addition, no two face-adjacent edges (consecutive edges of a facial trail of some face) receive the same color. The minimum number of colors used in such a coloring of G is denoted by afr'(G)
In this paper, we determine tight upper bounds for afr'(G).
Received: February 1, 2013
AMS Subject Classification: 05C10, 05C15
Key Words and Phrases: plane graph, facial cycle, edge-coloring
Download paper from here.
DOI: 10.12732/ijpam.v85i1.11 How to cite this paper?
Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2013
Volume: 85
Issue: 1
