• Laeeq Aslam

• Laeeq Aslam

• Shahzad Sarwar

• Muhammad Murtaza Yousaf

• Waqar ul Qounain

تلخیص

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 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.

اگلا مقالہ