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) 2n 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
2n 3 2
. Let
Gt
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
Gt
, cycdisc(G) 2 t 2
. Furthermore a graph G'
exists in
Gt
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.
Laeeq Aslam, Laeeq Aslam, Shahzad Sarwar, Muhammad Murtaza Yousaf, Waqar ul Qounain. (2016) Cycle Discrepancy of d-Colorable Graphs, Pakistan Journal of Engineering and Applied Sciences, VOLUME 18, Issue 1.
-
Views
2044 -
Downloads
158
Previous Article
Article Details
Volume
Issue
Type
Language
