Cycle Discrepancy of d-Colorable Graphs

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

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

Full Text:

PDF

References


S. Abbasi, L. Aslam, 2011, “The cycle discrepancy of three-regular graphs”,Graphs and Combinatorics, Vol. 27, pp. 27–46.

J. Beck, W. L. Chen, 1987, “Irregularities of distribution,” Cambridge University press, New York.

J. Beck, W. Fiala, 1981, “Integer making theorems”, Discrete Applied Mathematics, Vol. 3, pp. 1-8.

B. Bollobás, 1988, “Modern graph theory”, Springer-Verlag.

B. Chazelle, 2000, “The discrepancy method: randomness and complexity”, Cambridge University press, New York.

G. A. Dirac, 1952, “Some theorems on abstract graphs”, proc. London math. soc., Vol. s3-2, pp. 69-81.

J. Matousek, 1999, “Geometric discrepancy: an illustrated guide. Algorithms and combinatorics”, Springer, Berlin.

J. Spencer, 1985, “Six standard deviations suffice”, Transactions of the American mathematical society, Vol. 289, pp. 679-706.




Bookmark and Share


Copyright (c) 2016 Laeeq Aslam

Powered By KICS