IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

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

World University root node

Department of Mathematics

Discussiones Mathematicae - Graph Theory

Oriented colouring of some graph products

A 2-connected graph G is minimally 2-connected (m2c ) , if G - e contains a cut vertex for any edge e. Thus every edge is critical for the 2-connectivity. This class has been studied independently by Plummer [10] and Dirac [6] and they obtain some interesting structural properties of these classes. In the context of edge colouring problems, we revisit these results and this reveals some interesting structural properties which are useful in several graph colouring problems. We present the structural properties and application to 4 different problems viz. induced matching, acyclic and k-intersection edge colourings and balanced decomposition. The structure has similarity with structure of degenerate graphs and this enables one to also generalise some of these results to graphs of given degeneracy. All these results are co-authored by the author in [9,3,4,5]. In the following, d(x) is the degree of a vertex, Δ maximum degree. Vertices of degree at least, at most and equal to k are denoted k +, k-, k. For each connected graph we can find a block-cut-vertex tree which contains all cut-vertices and blocks of G and a cut-vertex v of G is adjacent to a block B of G whenever v ε V (B). An end block is a block containing at most one cut-vertex in G. Undefined terms can be found in standard textbooks in graph theory.

10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2011 - Proceedings of the Conference

Minimally 2-connected graphs and colouring problems

We present some classes of graphs which satisfy the acyclic edge colouring conjecture which states that any graph can be acyclically edge coloured with at most ∆ + 2 colours

Submitted

Some graph classes satisfying acyclic edge colouring conjecture

We determine the values of the acyclic chromatic index of a class of graphs referred to as d-dimensional partial tori. These are graphs which can be expressed as the cartesian product of d graphs each of which is an induced path or cycle. This class includes some known classes of graphs like d-dimensional meshes, hypercubes, tori, etc. Our estimates are exact except when the graph is a product of a path and a number of odd cycles, in which case the estimates differ by an additive factor of at most 1. Our results are also constructive and provide an optimal (or almost optimal) acyclic edge colouring in polynomial time. © 2010 Elsevier B.V. All rights reserved.

Fulltext

Discrete Mathematics

Optimal acyclic edge colouring of grid like graphs

Three graph colouring problems are studied in this thesis with the main focus on'acyclic edge colouring problem'. The first part of this thesis deals with some classes of graphs and improved upper bounds are obtained. The second part deals with k-intersection edge colouring. It aims to find the minimum number of colours that are sufficient to colour the edges such that for any pair of adjacent vertices, the number of common colours received on the edges incident on them is at most k.

HBNI

Acyclic, k-intersection edge colourings and oriented colouring [HBNI Th 14]

We propose the following problem. For some k≥ 1, a graph G is to be properly edge coloured such that any two adjacent vertices share at most k colours. We call this the k-intersection edge colouring. The minimum number of colours sufficient to guarantee such a colouring is the k-intersection chromatic index and is denoted χ′ k (G).

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

We propose the following problem. For some k ≥ 1, a graph G is to be properly edge coloured such that any two adjacent vertices share at most k colours. We call this the k-intersection edge colouring. The minimum number of colours sufficient to guarantee such a colouring is the k-intersection chromatic index and is denoted Xik(G). Let fk be defined by fk ($\delta$) = max/ G:$\delta$(G)=$\delta$ {Xik(G)}. We show that fk($\delta$) = $\theta$($\delta$ 2/k ). We also discuss some open problems.

On k-intersection edge colourings

An acyclic edge colouring of a graph is a proper edge colouring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge colouring using k colours and it is denoted by a ′ (G). Here, we obtain tight estimates on a ′ (G) for nontrivial subclasses of the family of 2-degenerate graphs. Specifically, we obtain values of the acyclic chromatic index for the families of partial 2-trees and series-parallel graphs. Another family contained within the family of 2-degenerate graphs is the family of outerplanar graphs. The acyclic chromatic index for outerplanar graphs has already been tightly determined. It was conjectured by Alon, Sudakov and Zaks that a ′ (G) ≤ ∆ + 2, where ∆ = ∆(G) denotes the maximum degree of the graph. Here we verify the conjecture for the classes of graphs considered. We first prove that a ′ (G) ≤ ∆ + 1 for partial 2-trees. As a corollary, it follows that the same bound holds for the class of series-parallel graphs, as it is a subclass of the class of partial 2-trees. These are best possible upper bounds, as there are examples graphs in the corresponding families which require that many colours for an acyclic edge colouring. All these bounds are proved constructively, leading to effecient algorithms to produce colourings with the stated number of colours.

Acyclic edge colouring of partial 2-trees

Let G = (V, E) be any finite simple graph. A mapping C : E → [k] is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced by all the edges which have either colour i or j is acyclic. The smallest number k of colours, such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G and is denoted by $\chi$a′ (G). In 1991, Alon et al. [N. Alon, C.J.H. McDiarmid, B.A. Reed, Acyclic coloring of graphs, Random Structures and Algorithms 2 (1991) 277-288] proved that $\chi$a′ (G) ≤ 64 $\Delta$ (G) for any graph G of maximum degree $\Delta$ (G). This bound was later improved to 16 $\Delta$ (G) by Molloy and Reed in [M. Molloy, B. Reed, Further algorithmic aspects of the local lemma, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 524-529]. In this paper we prove that $\chi$a′ (G) ≤ $\Delta$ (G) + 6 for a planar graph G without cycles of length three and that the same holds if G has an edge-partition into two forests. We also show that $\chi$a′ (G) ≤ 2 $\Delta$ (G) + 29 if G is planar. {\textcopyright} 2008 Elsevier B.V. All rights reserved.

Information Processing Letters

About acyclic edge colourings of planar graphs

We propose the following problem. A graph G is to be properly edge coloured such that any two adjacent vertices share at most k colours. We call this the k-intersection colouring. The minimum number of colours required for such a colouring is the k- intersection chromatic index and is denoted χ 0 k . Let f be defined by fk(∆) = max G:∆(G)=∆ {χ 0 k (G)} We show that fk(∆) = Θ( ∆2 k ). We also discuss some open problems.

k intersection colouring.

We prove that the acyclic chromatic index a′ (G) ≤ 6 Δ for all graphs with girth at least 9. We extend the same method to obtain a bound of 4.52 Δ with the girth requirement g ≥ 220. We also obtain a relationship between g and a′ (G). © 2007 Elsevier B.V. All rights reserved.

Improved bounds on acyclic edge colouring

An acyclic edge colouring of a graph is a proper edge colouring having no 2-coloured cycle, that is, a colouring in which the union of any two colour classes forms a linear forest. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge colouring using k colours and is usually denoted by a′(G). Determining a′(G) exactly is a very hard problem (both theoretically and algorithmically) and is not determined even for complete graphs. We show that a′(G) ≤ Δ(G) + 1, if G is an outerplanar graph. This bound is tight within an additive factor of 1 from optimality. Our proof is constructive leading to an O(n log Δ) time algorithm. Here, Δ = Δ(G) denotes the maximum degree of the input graph. © Springer-Verlag Berlin Heidelberg 2007.