IJPAM: Volume 106, No. 3 (2016)

EVEN VERTEX COLORING OF A GRAPH

P. Siva Kota Reddy$^1$, Kavita S. Permi$^2$
$^1$Department of Mathematics
Siddaganga Institute of Technology
B.H. Road, Tumkur, 572 103, INDIA
$^2$Department of Mathematics
Acharya Institute of Technology
Bangalore, 560 107, INDIA


Abstract. As a generalization of Harary's notion of consistency in marked graphs, we define define an even vertex coloring of a graph $G$ as an assignment of colors to the vertices of $G$ such that in every cycle of $G$ there is a nonzero even number of vertices of at least one color. The even vertex coloring number $\varepsilon_v(G)$ of even-vertex colorable graph $G$ is defined as the minimum number of colors in an even vertex coloring of $G$ and a minimum even vertex coloring of $G$ is is one which uses exactly $n = \varepsilon_v(G)$ colors. A characterization of minimally edge-colored graphs is obtained and a result linking the notion to bipartite Eulerian multigraphs is established.

Received: August 12, 2015

AMS Subject Classification: 05C22

Key Words and Phrases: coloring, marked graphs, consistency, even vertex coloring

Download paper from here.



DOI: 10.12732/ijpam.v106i3.5 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: 2016
Volume: 106
Issue: 3
Pages: 753 - 758


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

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