IJPAM: Volume 88, No. 2 (2013)

$M_2$-EDGE COLORING AND
MAXIMUM MATCHING OF GRAPHS

Kristína Budajová$^1$, Július Czap$^2$
$^1$Department of Aerodynamics and Simulations
Faculty of Aeronautics
Technical University of Košice
Rampová 7, SK-041 21 Košice, SLOVAKIA
$^2$Department 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 $\varphi$ of a graph $G$ is called $M_2$-edge coloring if $\vert\varphi(v)\vert\le2$ for every vertex $v$ of $G$, where $\varphi(v)$ is the set of colors of edges incident with $v$. Let $\alpha(G)$ denote the size of a maximum matching in $G$. Every graph $G$ with maximum degree at least 2 has an $M_2$-edge coloring with at least $\alpha(G)+1$ colors. We prove that this bound is tight even for connected planar graphs. We show that for any $n \in \mathbb N$ and $\delta \in \{1,2,3,4,5\}$ there is a connected planar graph $G$ on at least $n$ vertices with minimum degree $\delta$ such that the maximum number of colors used in an $M_2$-edge coloring of $G$ is equal to $\alpha(G)+1$.

Received: April 9, 2013

AMS Subject Classification: 05C15, 05C70

Key Words and Phrases: edge coloring, matching

Download paper from here.


DOI: 10.12732/ijpam.v88i2.1 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: 88
Issue: 2