A note on acyclic edge coloring of complete bipartite graphs


Autoria(s): Basavaraju, Manu; Chandran, L Sunil
Data(s)

01/07/2009

Resumo

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). Let Delta = Delta(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K-n,K-n. Alon, McDiarmid and Reed observed that a'(K-p-1,K-p-1) = p for every prime p. In this paper we prove that a'(K-p,K-p) <= p + 2 = Delta + 2 when p is prime. Basavaraju, Chandran and Kummini proved that a'(K-n,K-n) >= n + 2 = Delta + 2 when n is odd, which combined with our result implies that a'(K-p,K-p) = p + 2 = Delta + 2 when p is an odd prime. Moreover we show that if we remove any edge from K-p,K-p, the resulting graph is acyclically Delta + 1 = p + 1-edge-colorable. (C) 2009 Elsevier B.V. All rights reserved.

Formato

application/pdf

Identificador

http://eprints.iisc.ernet.in/21130/1/pdf.pdf

Basavaraju, Manu and Chandran, L Sunil (2009) A note on acyclic edge coloring of complete bipartite graphs. In: Discrete Mathematics, 309 (13). pp. 4646-4648.

Publicador

Elsevier Science BV

Relação

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V00-4VP172X-B&_user=512776&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000025298&_version=1&_urlVersion=0&_userid=512776&md5=7964bcde2769e9beec874e61183bae43

http://eprints.iisc.ernet.in/21130/

Palavras-Chave #Computer Science & Automation (Formerly, School of Automation)
Tipo

Journal Article

PeerReviewed