Faculty Publications

Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736

Publications by NITK Faculty

Browse

Author: search.filters.author.Sunil Chandran, L.Has files: No

Search Results

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    On Induced Colourful Paths in Triangle-free Graphs
    (Elsevier B.V., 2017) Babu, J.; Basavaraju, M.; Sunil Chandran, L.; Francis, M.C.
    Given a graph G=(V,E) whose vertices have been properly coloured, we say that a path in G is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy Theorem that every properly coloured graph contains a colourful path on ?(G) vertices. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on ?(G) vertices and prove its correctness when the girth of G is at least ?(G). Recent work on this conjecture by Gyárfás and Sárközy, and Scott and Seymour has shown the existence of a function f such that if ?(G)?f(k), then an induced colourful path on k vertices is guaranteed to exist in any properly coloured triangle-free graph G. © 2017 Elsevier B.V.
  • No Thumbnail Available
    Item
    Weak Total Coloring Conjecture and Hadwiger’s Conjecture on Total Graphs
    (Australian National University, 2024) Basavaraju, M.; Sunil Chandran, L.; Francis, M.C.; Naskar, A.
    The total graph of a graph G, denoted by T (G), is defined on the vertex set V (G) ∪ E(G) with c1, c2 ∈ V (G) ∪ E(G) adjacent whenever c1 and c2 are adjacent to (or incident on) each other in G. The total chromatic number χ′′ (G) of a graph G is defined to be the chromatic number of its total graph. The well-known Total Coloring Conjecture or TCC states that for every simple finite graph G having maximum degree ∆(G), χ′′ (G) ≤ ∆(G) + 2. In this paper, we consider two ways to weaken TCC: 1. Weak TCC: This conjecture states that for a simple finite graph G, χ′′ (G) = χ(T (G)) ≤ ∆(G)+3. While weak TCC is known to be true for 4-colorable graphs, it has remained open for 5-colorable graphs. In this paper, we settle this long pending case. 2. Hadwiger’s Conjecture for total graphs: We can restate TCC as a conjecture that proposes the existence of a strong χ-bounding function for the class of total graphs in the following way: If H is the total graph of a simple finite graph, then χ(H) ≤ ω(H) + 1, where ω(H) is the clique number of H. A natural way to relax this question is to replace ω(H) by the Hadwiger number η(H), the number of vertices in the largest clique minor of H. This leads to the Hadwiger’s Conjecture (HC) for total graphs: if H is a total graph then χ(H) ≤ η(H). We prove that this is true if H is the total graph of a graph with sufficiently large connectivity. It is known that (European Journal of Combinatorics, 76, 159–174,2019) if Hadwiger’s Conjecture is proved for the squares of certain special class of split graphs, then it holds also for the general case. The class of total graphs turns out to be the squares of graphs obtained by a natural structural modification of this type of split graphs. © The authors.