Cycle Discrepancy of d-Colorable Graphs

Laeeq Aslam; Shahzad Sarwar; Muhammad Murtaza Yousaf; Waqar ul Qounain

Author(s)

Laeeq Aslam Punjab University College of Information Technology(PUCIT), University of the Punjab, Lahore, Pakistan

Shahzad Sarwar Punjab University College of Information Technology(PUCIT), University of the Punjab, Lahore, Pakistan

Muhammad Murtaza Yousaf Punjab University College of Information Technology(PUCIT), University of the Punjab, Lahore, Pakistan

Waqar ul Qounain Punjab University College of Information Technology(PUCIT), University of the Punjab, Lahore, Pakistan

Abstract

We show that cycle discrepancy of a 3-colorable graph, G, on at least five vertices is bounded by 2 ´ éën 3û 2ù ; that is, cycdisc(G) £ 2 ´ éën 3û 2ù. We also show that this bound is best possible by constructing 3-colorable graphs, on at least five vertices for which cycle discrepancy is at least 2 ´ éën 3û 2ù . Let G t be the set of 3-colorable graphs on n = 5 vertices with t vertices in the smallest color class. We show that for a graph, G from G t , cycdisc(G) £ 2 ´ ét 2ù . Furthermore a graph G' exists in G t with large cycle discrepancy, such that cycdisc (G' ) ³ 2 ´ ét 2ù for t = 1. We also construct such d-colorable graphs for d> 3 that have maximum possible cycle discrepancy.

Publication Details

Page(s) 50-55

DOI DOI not available

Published Journal: Pakistan Journal of Engineering and Applied Sciences, Volume: 18, Issue: 0, Year: 2016

Request the full text from PASTIC

Keywords

Cycle discrepancy, Graph coloring