Abstract:

A proper edge-coloring of a graph G is a mapping α : E(G) → N such that α(e) 6= α(e 0 ) for every pair of adjacent edges e, e0 ∈ E(G). If α is a proper edgecoloring of a graph G and v ∈ V (G), then the palette of a vertex v, denoted by P (v, α), is the set of all colors appearing on edges incident to v. The palette index of a graph G, denoted by ˇs(G), is the minimum number of distinct palettes taken over all proper edge-colorings of G. In this paper we investigate the palette index of bipartite graphs. In particular, we prove that: 1) if G is a bipartite graph with ∆(G) = 4, then ˇs(G) ≤ 11, and moreover if G is a bipartite graph with ∆(G) = 4 and without pendant vertices, then ˇs(G) ≤ 7; 2) if G is an Eulerian bipartite graph with ∆(G) ≤ 6, then sˇ(G) ≤ 7; 3) if G is an Eulerian bipartite graph with ∆(G) = 8, then ˇs(G) ≤ 13. We also obtain some results on the palette index of (a, b)-biregular bipartite graphs. In particular, we prove that if G is a (2, 2r)-biregular (r ≥ 2) bipartite graph, then ˇs(G) = r + 1, if G is a (2, 2r + 1)-biregular (r ∈ N) bipartite graph, then r+ 2 ≤ sˇ(G) ≤ 2r+ 2, and if G is a (2r−2, 2r)-biregular (r ≥ 2) bipartite graph, then ˇs(G) = r + 1.

Identifier:

oai:noad.sci.am:135779

Language:

English

URL:

Affiliation:

Institute for Informatics and Automation Problems ; Yerevan State University ; Department of Informatics and Applied Mathematics

Country:

Armenia

Year:

2017

Time period:

September25-29

Conference title:

11th International Conference on Computer Science and Information Technologies CSIT 2017

Place:

Yerevan

Participation type:

oral