IJPAM: Volume 115, No. 1 (2017)

Title

FACIAL TOTAL-COLORING OF BIPARTITE PLANE GRAPHS

Authors

Július Czap$^1$, Peter Šugerek$^2$
$^{1,2}$Department of Applied Mathematics and Business Informatics
Faculty of Economics
Technical University of Košice
Němcovej 32, 040 01 Košice, SLOVAKIA

Abstract

Let $G$ be a plane graph. Two edges are facially adjacent in $G$ if they are consecutive edges on a boundary walk of a face of $G$. A facial edge-coloring of $G$ is an edge-coloring such that any two facially adjacent edges receive distinct colors. A facial total-coloring of $G$ is a coloring of vertices and edges such that no facially adjacent edges, no adjacent vertices, and no edge and its endvertices are assigned the same color. In this paper we prove that every plane graph admits a facial edge-coloring with at most four colors such that at most three colors appear at each vertex. Using this result we confirm a conjecture on facial total-coloring for bipartite plane graphs.

History

Received: May 3, 2017
Revised: June 13, 2017
Published: June 29, 2017

AMS Classification, Key Words

AMS Subject Classification: 05C10, 05C15
Key Words and Phrases: plane graph, total-coloring

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
K. Appel, W. Haken, Every planar map is four colorable, Part I: Discharging, Illinois J. Math., 21 (1977), 429-490.

2
K. Appel, W. Haken, J. Koch, Every planar map is four colorable, Part II: Reducibility, Illinois J. Math., 21 (1977), 491-567.

3
J.A. Bondy, U.S.R. Murty, Graph Theory, Springer (2008), doi: https://doi.org/10.1007/978-1-84628-970-5.

4
J. Czap, S. Jendroľ, Facially-constrained colorings of plane graphs: A survey, Discrete Math., (2016) in press, doi: https://doi.org/10.1016/j.disc.2016.07.026.

5
I. Fabrici, S. Jendroľ, M. Voigt, Facial list colourings of plane graphs, Discrete Math., 339 (2016), 2826-2831, doi: https://doi.org/10.1016/j.disc.2016.05.034.

6
I. Fabrici, S. Jendroľ, M. Vrbjarová, Facial entire colouring of plane graphs, Discrete Math., 339 (2016), 626-631, doi: https://doi.org/10.1016/j.disc.2015.09.011.

7
J.L. Gross, T.W. Tucker, Topological Graph Theory, Dover Publications (2001).

8
N. Robertson, D.P. Sanders, P.D. Seymour, R. Thomas, The four-colour theorem, J. Combin. Theory Ser. B, 70 (1997), 2-44, doi: https://doi.org/10.1006/jctb.1997.1750.

How to Cite?

DOI: 10.12732/ijpam.v115i1.9 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: 2017
Volume: 115
Issue: 1
Pages: 115 - 121


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).