Indian Institute of Technology Hyderabad (IITH) is a premier institute of science and technology established in 2008. IITH has been consistently ranked in the&nbsp;<a href="https://iith.ac.in/reports/" rel="noopener noreferrer">top 10 institutes</a>&nbsp;in India for Engineering&nbsp;<a href="https://www.nirfindia.org/2021/EngineeringRanking.html" rel="noopener noreferrer" target="_blank">according to NIRF</a>&nbsp;making it one of the most coveted schools for science and technology in the country.

IITH offers&nbsp;<a href="https://iith.ac.in/academics/under-graduate/">undergraduate programs</a>&nbsp;in all the classical engineering disciplines, applied sciences, design, as well as several modern interdisciplinary areas. Students are given a flexibility to explore a broad set of areas, and potentially pursue a minor or double major in a discipline that is not their own. Students who wish to seek a deeper understanding of their own discipline are strongly encouraged to get involved in cutting-edge research with the help of a faculty to mentor them, and earn an Honors in their own field.

The very foundation of IIT Hyderabad is based on&nbsp;<a href="https://iith.ac.in/research/">research and innovation</a>. The vibrant research culture is evident from the number of patents and publications that IITH produces consistently every year. IITH offers&nbsp;<a href="https://iith.ac.in/academics/programmes-offered/">graduate programs</a>&nbsp;at both a masters, and a doctoral level, in several diverse areas. There are separate programs for technology, design, science, and liberal arts. The&nbsp;<a href="https://iith.ac.in/academics/post-graduate/">MTech program</a>&nbsp;is offered in various modes and durations to cater to the ever-growing need of postgraduate level professionals in the country.

IITH encourages and supports&nbsp;<a href="https://iic-iith.netlify.app/index.html" rel="noopener noreferrer" target="_blank">innovation and entrepreneurship</a>&nbsp;at every stage. The minor program in entrepreneurship is open to all students of IITH, and many of the courses are offered by industrialists who are entrepreneurs themselves. There are various&nbsp;<a href="https://iith.ac.in/research/centres-incubators/">innovation centers and incubators</a>&nbsp;that promote entrepreneurship and help mentor young innovators. IITH has been very successful in building tie-ups with leading academic institutions around the globe.

IITH enjoys a very special relationship with Japanese universities and industries that goes beyond academic and research collaborations. In fact, some of the iconic buildings in IITH campus will carry the signature of Japanese architecture.

IITH creates a unique holistic ecosystem for education that offers interactive learning, a very flexible academic structure, cutting-edge research, strong industry collaboration, and entrepreneurship. This is an environment which enables students and faculty to translate their dreams into realities.

IIT Hyderabad

We present an improved upper bound of O(d1+[Formula presented]) for the (2,F)-subgraph chromatic number χ2,F(G) of any graph G of maximum degree d. Here, m denotes the minimum number of edges in any member of F. This bound is tight up to a (logd)1/(m−1) multiplicative factor and improves the previous bound presented in Aravind and Subramanian (2011) [5]. Along the way, we state and prove an easy-to-use version of the Lovász Local Lemma. We also obtain a relationship connecting the oriented chromatic number χo(G) of graphs and the (j,F)-subgraph chromatic numbers χj,F(G) introduced and studied in Aravind and Subramanian (2011) [5]. In particular, we relate the oriented chromatic number and the (2,r)-treewidth chromatic number and show that χo(G)≤k((r+1)2r)k−1 for any graph G having (2,r)-treewidth chromatic number at most k. The latter parameter is the least number of colors in any proper vertex coloring which is such that the subgraph induced by the union of any two color classes has treewidth at most r. We also generalize a result of Alon et al. (1996) [3] on acyclic chromatic number of graphs on surfaces (with characteristic −γ≤0) to (2,F)-subgraph chromatic numbers and prove that χ2,F(G)=O(γm/(2m−1)) for some constant m depending only on F. We also show that this bound is nearly tight. We then use this result to show that graphs of genus g have oriented chromatic number at most 2O(g1/2+ϵ) for every fixed ϵ&gt;0. We also refine the proof of a bound on χo(G) obtained by Kostochka et al. (1997) in [10] to obtain an improved bound on χo(G). © 2012 Elsevier Ltd

Department of Computer Science and Engineering

World University root node

European Journal of Combinatorics

Forbidden subgraph colorings and the oriented chromatic number

Reed [B. Reed, ω,Δ and χ, Journal of Graph Theory, 27 (1998) 177-212] conjectured that for any graph G, χ(G)≤Δ(G) +ω(G)+12⌉, where χ(G), ω(G), and Δ(G) respectively denote the chromatic number, the clique number and the maximum degree of G. In this paper, we verify this conjecture for some special classes of graphs which are defined by families of forbidden induced subgraphs. © 2011 Elsevier B.V. All rights reserved.

Discrete Mathematics

Bounding χ in terms of ω and Δ for some classes of graphs

We obtain some improved upper and lower bounds on the oriented chromatic number for different classes of products of graphs.

Fulltext

Discussiones Mathematicae - Graph Theory

Oriented colouring of some graph products

A proper coloring of a graph is a labeled partition of its vertices into parts which are independent sets. In this paper, given a positive integer j and a family F of connected graphs, we consider proper colorings in which we require that the union of any j color classes induces a subgraph which has no copy of any member of F. This generalizes some well-known types of proper colorings like acyclic colorings (where j = 2 and Fis the collection of all even cycles) and star colorings (where j = 2 and Fconsists of just a path on 4 vertices), etc. For this type of coloring, we obtain an upper bound of O(d (k - 1)/(k - j)) on the minimum number of colors sufficient to obtain such a coloring. Here, d refers to the maximum degree of the graph and k is the size of the smallest member of F. For the case of j = 2, we also obtain lower bounds on the minimum number of colors needed in the worst case. As a corollary, we obtain bounds on the minimum number of colors sufficient to obtain proper colorings in which the union of any j color classes is a graph of bounded treewidth. In particular, using O(d8/7) colors, one can obtain a proper coloring of the vertices of a graph so that the union of any two color classes has treewidth at most 2. We also show that this bound is tight within a multiplicative factor of O((logd)1/7). We also consider generalizations where we require simultaneously for several pairs (j i, Fi) (i = 1, ..., l) that the union of any ji color classes has no copy of any member of Fi and obtain upper bounds on the corresponding chromatic numbers. © 2011 Wiley Periodicals, Inc.

Journal of Graph Theory

Bounds on vertex colorings with restrictions on the union of color classes

We consider constrained proper edge colorings of the following type: Given a positive integer j and a family F of connected graphs on three or more vertices, we require that the subgraph formed by the union of any j color classes has no copy of any member of F. This generalizes some well-known types of colorings such as acyclic edge colorings, distance-2 edge colorings, low treewidth edge colorings, etc. For such a generalization of restricted colorings, we obtain an upper bound of O(dmax(θ,1)) on the minimum number of colors used in such a coloring. Here d refers to the maximum degree of the graph, and θ is a parameter defined by θ = θ(j,F) = SUPh ∈F (|V(H) |-2)/(|E(H)|-J), where SUP stands for the supremum. Our proof is based on probabilistic arguments. In particular, we obtain O(d) upper bounds for proper edge colorings with various interesting restrictions placed on the union of color classes. For example, we obtain O(d) upper bounds on edge colorings with restrictions such as (i) the union of any three color classes should be an outerplanar graph, (ii) the union of any four color classes should have treewidth at most 2, (iii) the union of any five color classes should be planar, (iv) the union of any 16 color classes should be 5-degenerate, etc. We also consider generalizations where we require simultaneously for several pairs (ji, Fi) (i = 1,..., s) that the union of any ji color classes has no copy of any member of Fi and obtain upper bounds on the corresponding chromatic indices. As a corollary, we obtain that each of the four restrictions above can be satisfied simultaneously using O(d) colors. Some ways of improving the bounds are sketched. Also, if we drop the requirement that the edge coloring be proper, then an O(dθ) upper bound on the chromatic index is established. Further, the stated upper bounds are also bounds for the list analogues of these edge colorings. © 2010 Society for Industrial and Applied Mathematics.

SIAM Journal on Discrete Mathematics

Bounds on edge colorings with restrictions on the union of color classes

We show that the intersection dimension of graphs with respect to several hereditary properties can be bounded as a function of the maximum degree. As an interesting special case, we show that the circular dimension of a graph with maximum degree Δ is at most O (Δ frac(log Δ, log log Δ)). We also obtain bounds in terms of treewidth. © 2009 Elsevier B.V. All rights reserved.

Electronic Notes in Discrete Mathematics

Intersection Dimension and Maximum Degree

We present an improved upper bound of O(d1+ 1/m-1) for the (2,F)-subgraph chromatic number X2,F(G) of any graph G of maximum degree d. Here, m denotes the minimum number of edges in any member of F. This bound is tight up to a (log d)1/(m-1) multiplicative factor and improves the previous bound presented in [1]. We also obtain a relationship connecting the oriented chromatic number Xo(G) of graphs and the (j,F)-subgraph chromatic numbers Xj,F(G) introduced and studied in [1]. In particular, we relate oriented chromatic number and the (2, r)-treewidth chromatic number and show that Xo(G) ≤ k ((r + 1)2r)k-1 for any graph G having (2, r)-treewidth chromatic number at most k. The latter parameter is the least number of colors in any proper vertex coloring which is such that the subgraph induced by the union of any two color classes has treewidth at most r.We also generalize a result of Alon, et. al. [2] on acyclic chromatic number of graphs on surfaces to (2,F)-subgraph chromatic numbers and prove that X2,F(G) = O(γm/(2m-1)) for some constant m depending onlyon F. We also show that this bound is nearly tight. We then use this result to show that graphs of genus g have oriented chromatic number at most 2 O(g1/2+ε) for every fixed ε &gt; 0. This improves the previously known bound of 2O(g4/7). We also refine the proof of a bound on Xo(G) obtained by Kostochka, et. al. in [3] to obtain an improved bound on Xo(G). © Springer-Verlag Berlin Heidelberg 2009.