Browsing by Author "Basavaraju, M."

Now showing 1 - 19 of 19

Acyclic chromatic index of chordless graphs
(Elsevier B.V., 2023) Basavaraju, M.; Hegde, S.M.; Kulamarva, S.
An acyclic edge coloring of a graph is a proper edge coloring with no bichromatic cycles. The acyclic chromatic index of a graph G denoted by a′(G), is the minimum integer k such that G has an acyclic edge coloring with k colors. It was conjectured by Fiamčík [13] that a′(G)≤Δ+2 for any graph G with maximum degree Δ. Linear arboricity of a graph G, denoted by la(G), is the minimum number of linear forests into which the edges of G can be partitioned. A graph is said to be chordless if no cycle in the graph contains a chord. By a result of Basavaraju and Chandran [6], if G is chordless, then a′(G)≤Δ+1. Machado, de Figueiredo and Trotignon [23] proved that the chromatic index of a chordless graph is Δ when Δ≥3. We prove that for any chordless graph G, a′(G)=Δ, when Δ≥3. Notice that this is an improvement over the result of Machado et al., since any acyclic edge coloring is also a proper edge coloring and we are using the same number of colors. As a byproduct, we prove that [Formula presented], when Δ≥3. To obtain the result on acyclic chromatic index, we prove a structural result on chordless graphs which is a refinement of the structure given by Machado et al. [23] in case of chromatic index. This might be of independent interest. © 2023 Elsevier B.V.
Gallai’s Path Decomposition for 2-degenerate Graphs
(Discrete Mathematics and Theoretical Computer Science, 2023) Anto, N.; Basavaraju, M.
Gallai’s path decomposition conjecture states that if G is a connected graph on n vertices, then the edges of G can be decomposed into at most ⌈ n2 ⌉ paths. A graph is said to be an odd semi-clique if it can be obtained from a clique on 2k + 1 vertices by deleting at most k − 1 edges. Bonamy and Perrett asked if the edges of every connected graph G on n vertices can be decomposed into at most ⌊ n2 ⌋ paths unless G is an odd semi-clique. A graph G is said to be 2-degenerate if every subgraph of G has a vertex of degree at most 2. In this paper, we prove that the edges of any connected 2-degenerate graph G on n vertices can be decomposed into at most ⌊ n2 ⌋ paths unless G is a triangle. © 2023 by the author(s)
Maximal induced matchings in K4-free and K5-free graphs
(Elsevier B.V., 2024) Basavaraju, M.; van Leeuwen, E.J.; Saei, R.
An induced matching in a graph is a set of edges whose endpoints induce a 1-regular subgraph. It is known that every graph on n vertices has at most 10n/5?1.5849n maximal induced matchings, and this bound is the best possible as any disjoint union of complete graphs K5 forms an extremal graph. It is also known that the bound drops to 3n/3?1.4423n when the graphs are restricted to the class of triangle-free (K3-free) graphs. The extremal graphs, in this case, are known to be the disjoint unions of copies of K3,3. Along the same line, we study the maximum number of maximal induced matchings when the graphs are restricted to K5-free graphs and K4-free graphs. We show that every K5-free graph on n vertices has at most 6n/4?1.5651n maximal induced matchings and the bound is the best possible obtained by any disjoint union of copies of K4. When the graphs are restricted to K4-free graphs, the upper bound drops to 8n/5?1.5158n, and it is achieved by the disjoint union of copies of the wheel graph W5. © 2024 The Author(s)
Maximal Induced Matchings in Triangle-Free Graphs
(Wiley-Liss Inc. info@wiley.com, 2016) Basavaraju, M.; Heggernes, P.; van 't'Hof, P.; Saei, R.; Villanger, Y.
An induced matching in a graph is a set of edges whose endpoints induce a 1-regular subgraph. It is known that every n-vertex graph has at most (Formula presented.) maximal induced matchings, and this bound is the best possible. We prove that every n-vertex triangle-free graph has at most (Formula presented.) maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K3, 3. Our result implies that all maximal induced matchings in an n-vertex triangle-free graph can be listed in time (Formula presented.), yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph. © 2015 Wiley Periodicals, Inc.
On induced colourful paths in triangle-free graphs
(Elsevier B.V., 2019) Babu, J.; Basavaraju, M.; Sunil Chandran, L.S.; 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–Vitaver 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. © 2018 Elsevier B.V.
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.
On the kernelization complexity of string problems
(Elsevier B.V., 2018) Basavaraju, M.; Panolan, F.; Rai, A.; Ramanujan, M.S.; Saurabh, S.
In the CLOSEST STRING problem we are given an alphabet ?, a set of strings S={s1,s2,…,sk} over ? such that |si|=n and an integer d. The objective is to check whether there exists a string s over ? such that dH(s,si)?d, i?{1,…,k}, where dH(x,y) denotes the number of places strings x and y differ at. CLOSEST STRING is a prototype string problem. This problem together with several of its variants such as DISTINGUISHING STRING SELECTION and CLOSEST SUBSTRING have been extensively studied from parameterized complexity perspective. These problems have been studied with respect to parameters that are combinations of k, d, |?| and n. However, surprisingly the kernelization question for these problems (for the versions when they admit fixed-parameter tractable algorithms) is not studied at all. In this paper we fill this gap in the literature and do a comprehensive study of these problems from kernelization complexity perspective. We settle almost all the problems by either obtaining a polynomial kernel or showing that the problem does not admit a polynomial kernel under a standard assumption in complexity theory. © 2018 Elsevier B.V.
Parameterized algorithms for survivable network design with uniform demands
(2018) Bang-Jensen, J.; Basavaraju, M.; Klinkby, K.V.; Misra, P.; Ramanujan, M.S.; Saurabh, S.; Zehavi, M.
In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruv for every pair of vertices u; v 2 V (G). The objective is to construct a subgraph H of minimum weight which contains ruv edge-disjoint (or node-disjoint) u-v paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. Consequently, there is a long line of research into exact-polynomial time algorithms as well as approximation algorithms for various restrictions of this problem. An important restriction of this problem is one where the connectivity demands are the same for every pair of vertices. In this paper, we first consider the edge-connectivity version of this problem which we call ?-Edge Connected Subgraph ( ?-ECS). In this problem, the input is a ?-edge connected (di)graph G and an integer k and the objective is to check whether G contains a spanning subgraph H that is also ?-edge connected and H excludes at least k edges of G. In other words, we are asked to compute a maximum subset of edges, of cardinality at least k, which may be safely deleted from G without affecting its connectivity. If we replace ?-edge connectivity with ?-vertex connectivity we get the ?-Vertex Connected Subgraph ( ?-VCS) problem. We show that ?-ECS is fixed-parameter tractable (FPT) for both graphs and digraphs even if the (di)graph has nonnegative real weights on the edges and the objective is to exclude from H, some edges of G whose total weight exceeds a prescribed value. In particular, we design an algorithm for the weighted variant of the problem with running time 2O(k log k)jV (G)jO(1). We follow up on this result and obtain a polynomial compression for ?-ECS on unweighted graphs. As a direct consequence of our results, we obtain the first FPT algorithm for the parameterized version of the classical Minimum Equivalent Graph (MEG) problem. We also show that ?-VCS is FPT on digraphs; however the problem on undirected graphs remains open. Finally, we complement our algorithmic findings by showing that SNDP is W[1]-hard for both arc and vertex connectivity versions on digraphs. The core of our algorithms is composed of new combinatorial results on connectivity in digraphs and undirected graphs. � Copyright 2018 by SIAM.
Parameterized algorithms for survivable network design with uniform demands
(Association for Computing Machinery acmhelp@acm.org, 2018) Bang-Jensen, J.; Basavaraju, M.; Klinkby, K.V.; Misra, P.; Ramanujan, M.S.; Saurabh, S.; Zehavi, M.
In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruv for every pair of vertices u; v 2 V (G). The objective is to construct a subgraph H of minimum weight which contains ruv edge-disjoint (or node-disjoint) u-v paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. Consequently, there is a long line of research into exact-polynomial time algorithms as well as approximation algorithms for various restrictions of this problem. An important restriction of this problem is one where the connectivity demands are the same for every pair of vertices. In this paper, we first consider the edge-connectivity version of this problem which we call Î»-Edge Connected Subgraph ( Î»-ECS). In this problem, the input is a Î»-edge connected (di)graph G and an integer k and the objective is to check whether G contains a spanning subgraph H that is also Î»-edge connected and H excludes at least k edges of G. In other words, we are asked to compute a maximum subset of edges, of cardinality at least k, which may be safely deleted from G without affecting its connectivity. If we replace Î»-edge connectivity with Î»-vertex connectivity we get the Î»-Vertex Connected Subgraph ( Î»-VCS) problem. We show that Î»-ECS is fixed-parameter tractable (FPT) for both graphs and digraphs even if the (di)graph has nonnegative real weights on the edges and the objective is to exclude from H, some edges of G whose total weight exceeds a prescribed value. In particular, we design an algorithm for the weighted variant of the problem with running time 2O(k log k)jV (G)jO(1). We follow up on this result and obtain a polynomial compression for Î»-ECS on unweighted graphs. As a direct consequence of our results, we obtain the first FPT algorithm for the parameterized version of the classical Minimum Equivalent Graph (MEG) problem. We also show that Î»-VCS is FPT on digraphs; however the problem on undirected graphs remains open. Finally, we complement our algorithmic findings by showing that SNDP is W[1]-hard for both arc and vertex connectivity versions on digraphs. The core of our algorithms is composed of new combinatorial results on connectivity in digraphs and undirected graphs. Â© Copyright 2018 by SIAM.
Partially polynomial kernels for set cover and test cover
(Society for Industrial and Applied Mathematics Publications support@jstor.org, 2016) Basavaraju, M.; Francis, M.C.; Ramanujan, M.S.; Saurabh, S.
An instance of the (n-k)-Set Cover or the (n-k)-Test Cover problems is of the form (U, S, k), where U is a set with n elements, S ? 2U with |S| = m, and k is the parameter. The instance is a Yes-instance of (n - k)-Set Cover if and only if there exists S' ? S with |S'| ? n - k such that every element of U is contained in some set in S'. Similarly, it is a Yes-instance of (n - k)-Test Cover if and only if there exists S' ? S with |S'| ? n - k such that for any pair of elements from U, there exists a set in S' that contains one of them but not the other. It is known in the literature that both (n - k)-Set Cover and (n - k)-Test Cover do not admit polynomial kernels (under some well-known complexity theoretic assumptions). However, in this paper we show that they do admit \partially polynomial kernels": we give polynomial time algorithms that take as input an instance (U, S, k) of (n - k)-Set Cover (respectively, (n - k)-Test Cover) and return an equivalent instance (U, S, k) of (n-k)-Set Cover (respectively, (n-k)-Test Cover) with k ? k and |?| = O(k2) (respectively, |?| = O(k7)). These results allow us to generalize, improve, and unify several results known in the literature. For example, these immediately imply traditional kernels when input instances satisfy certain \sparsity properties." Using a part of our partial kernelization algorithm for (n - k)-Set Cover, we also get an improved fixed-parameter tractable algorithm for this problem which runs in time O(4kkO(1)(m + n) + mn) improving over the previous best of O(8k+o(k)(m+n)O(1)). On the other hand, the partially polynomial kernel for (n-k)-Test Cover gives an algorithm with running time O(2O(k2)(m + n)O(1)). We believe such an approach could also be useful for other covering problems. © © by SIAM.
Ramsey Numbers for Line Graphs
(2020) Abbasi, H.; Basavaraju, M.; Gurushankar, E.; Jivani, Y.; Srikanth, D.
Given a graph, the classical Ramsey number R(k,�l) is the least number of vertices that need to be in the graph for the existence of a clique of size k or an independent set of size l. Finding R(k,�l) exactly has been a notoriously hard problem. Even R(k,�3) has not been determined for all values of k. Hence finding the Ramsey number for subclasses of graphs is an interesting question. It is known that even for claw-free graphs, finding Ramsey number is as hard as for general graphs for infinite number of cases. Line graphs are an important subclass of claw-free graphs. The question with respect to line graph L(G) is equivalent to the minimum number of edges the underlying graph G needs to have for the existence of a vertex with degree k or a matching of size l. Chv�tal and Hanson determined this exactly for line graphs of simple graphs. Later Balachandran and Khare gave the same bounds with a different proof. In this paper we find Ramsey numbers for line graph of multi graphs thereby extending the results of Chv�tal and Hanson. Here we determine the maximum number of edges that a multigraph can have, when its matching number, multiplicity, and maximum degree are bounded, and characterize such graphs. � 2020, Springer Nature Switzerland AG.
Ramsey Numbers for Line Graphs
(Springer, 2020) Abbasi, H.; Basavaraju, M.; Gurushankar, E.; Jivani, Y.; Srikanth, D.
Given a graph, the classical Ramsey number R(k,Â l) is the least number of vertices that need to be in the graph for the existence of a clique of size k or an independent set of size l. Finding R(k,Â l) exactly has been a notoriously hard problem. Even R(k,Â 3) has not been determined for all values of k. Hence finding the Ramsey number for subclasses of graphs is an interesting question. It is known that even for claw-free graphs, finding Ramsey number is as hard as for general graphs for infinite number of cases. Line graphs are an important subclass of claw-free graphs. The question with respect to line graph L(G) is equivalent to the minimum number of edges the underlying graph G needs to have for the existence of a vertex with degree k or a matching of size l. ChvÃ¡tal and Hanson determined this exactly for line graphs of simple graphs. Later Balachandran and Khare gave the same bounds with a different proof. In this paper we find Ramsey numbers for line graph of multi graphs thereby extending the results of ChvÃ¡tal and Hanson. Here we determine the maximum number of edges that a multigraph can have, when its matching number, multiplicity, and maximum degree are bounded, and characterize such graphs. Â© 2020, Springer Nature Switzerland AG.
Separation dimension and sparsity
(Wiley-Liss Inc. info@wiley.com, 2018) Alon, N.; Basavaraju, M.; Sunil Chandran, L.S.; Mathew, R.; Rajendraprasad, D.
The separation dimension ???(G) of a hypergraph G is the smallest natural number k for which the vertices of G can be embedded in Rk so that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the cardinality of a smallest family F of total orders of V(G), such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. Separation dimension is a monotone parameter; adding more edges cannot reduce the separation dimension of a hypergraph. In this article, we discuss the influence of separation dimension and edge-density of a graph on one another. On one hand, we show that the maximum separation dimension of a k-degenerate graph on n vertices is O(k lg lg n) and that there exists a family of 2-degenerate graphs with separation dimension ?(lg lg n). On the other hand, we show that graphs with bounded separation dimension cannot be very dense. Quantitatively, we prove that n-vertex graphs with separation dimension s have at most 3(4 lg n)s?2 edges. We do not believe that this bound is optimal and give a question and a remark on the optimal bound. © 2018 Wiley Periodicals, Inc.
Separation Dimension of Graphs and Hypergraphs
(Springer New York LLC barbara.b.bertram@gsk.com, 2016) Basavaraju, M.; Sunil Chandran, L.S.; Golumbic, M.C.; Mathew, R.; Rajendraprasad, D.
Separation dimension of a hypergraph H, denoted by ?( H) , is the smallest natural number k so that the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph H is equal to the boxicity of the line graph of H. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension. In this paper, we study the separation dimension of hypergraphs and graphs. © 2015, Springer Science+Business Media New York.
The Linear Arboricity Conjecture for 3-Degenerate Graphs
(Springer Science and Business Media Deutschland GmbH info@springer-sbm.com, 2020) Basavaraju, M.; Bishnu, A.; Francis, M.; Pattanayak, D.
A k-linear coloring of a graph G is an edge coloring of G with k colors so that each color class forms a linear forestâ€”a forest whose each connected component is a path. The linear arboricity Ï‡lâ€²(G) of G is the minimum integer k such that there exists a k-linear coloring of G. Akiyama, Exoo and Harary conjectured in 1980 that for every graph G, Ï‡lâ€²(G)â‰¤⌈Î”(G)+12⌉ where Î”(G) is the maximum degree of G. We prove the conjecture for 3-degenerate graphs. This establishes the conjecture for graphs of treewidth at most 3 and provides an alternative proof for the conjecture for triangle-free planar graphs. Our proof also yields an O(n)-time algorithm that partitions the edge set of any 3-degenerate graph G on n vertices into at most ⌈Î”(G)+12⌉ linear forests. Since Ï‡lâ€²(G)â‰¥⌈Î”(G)2⌉ for any graph G, the partition produced by the algorithm differs in size from the optimum by at most an additive factor of 1. Â© 2020, Springer Nature Switzerland AG.
Upper bounds on the acyclic chromatic index of degenerate graphs
(Elsevier B.V., 2024) Anto, N.; Basavaraju, M.; Hegde, S.M.; Kulamarva, S.
An acyclic edge coloring of a graph is a proper edge coloring without any bichromatic cycles. The acyclic chromatic index of a graph G denoted by a′(G), is the minimum k such that G has an acyclic edge coloring with k colors. Fiamčík [10] conjectured that a′(G)≤Δ+2 for any graph G with maximum degree Δ. A graph G is said to be k-degenerate if every subgraph of G has a vertex of degree at most k. Basavaraju and Chandran [4] proved that the conjecture is true for 2-degenerate graphs. We prove that for a 3-degenerate graph G, a′(G)≤Δ+5, thereby bringing the upper bound closer to the conjectured bound. We also consider k-degenerate graphs with k≥4 and give an upper bound for the acyclic chromatic index of the same. © 2024 Elsevier B.V.
Variants of the Gyárfás–Sumner conjecture: Oriented trees and rainbow paths
(John Wiley and Sons Inc, 2025) Basavaraju, M.; Sunil Chandran, L.S.; Francis, M.C.; Murali, K.
Given a finite family (Formula presented.) of graphs, we say that a graph (Formula presented.) is “ (Formula presented.) -free” if (Formula presented.) does not contain any graph in (Formula presented.) as a subgraph. We abbreviate (Formula presented.) -free to just “ (Formula presented.) -free” when (Formula presented.). A vertex-colored graph (Formula presented.) is called “rainbow” if no two vertices of (Formula presented.) have the same color. Given an integer (Formula presented.) and a finite family of graphs (Formula presented.), let (Formula presented.) denote the smallest integer such that any properly vertex-colored (Formula presented.) -free graph (Formula presented.) having (Formula presented.) contains an induced rainbow path on (Formula presented.) vertices. Scott and Seymour showed that (Formula presented.) exists for every complete graph (Formula presented.). A conjecture of N. R. Aravind states that (Formula presented.). The upper bound on (Formula presented.) that can be obtained using the methods of Scott and Seymour setting (Formula presented.) are, however, super-exponential. Gyárfás and Sárközy showed that (Formula presented.). For (Formula presented.), we show that (Formula presented.) and therefore, (Formula presented.). This significantly improves Gyárfás and Sárközy's bound and also covers a bigger class of graphs. We adapt our proof to achieve much stronger upper bounds for graphs of higher girth: we prove that (Formula presented.), where (Formula presented.). Moreover, in each case, our results imply the existence of at least (Formula presented.) distinct induced rainbow paths on (Formula presented.) vertices. Along the way, we obtain some new results on an oriented variant of the Gyárfás–Sumner conjecture. For (Formula presented.), let (Formula presented.) denote the orientations of (Formula presented.) in which one vertex has out-degree or in-degree (Formula presented.). We show that every (Formula presented.) -free oriented graph having a chromatic number at least (Formula presented.) and every bikernel-perfect oriented graph with girth (Formula presented.) having a chromatic number at least (Formula presented.) contains every oriented tree on at most (Formula presented.) vertices as an induced subgraph. © 2024 Wiley Periodicals LLC.
Vehicular Pollution and Its Relationship with Meteorological Variables at Toll Plaza During Paryaya Festival in Udupi, Karnataka
(Springer Science and Business Media Deutschland GmbH, 2024) Charly, T.; Basavaraju, M.; Mulangi, R.H.
The quantification of both air pollutants and noise is important to understand the impact of festival on pollution at toll plaza. Toll plazas can cause deterioration of air quality due to increased emission of pollutants caused by stop and go process. The present study was conducted at a toll plaza in front of National Institute of Technology, Karnataka, which is 39Â kms from Udupi, Karnataka, to assess the impact of vehicular movement due to Paryaya festival, which was on the third week of January 2020 at Udupi, on noise and air pollution at study area. Data regarding meteorological parameters and traffic volume were also considered during the study. Experiments were carried out at toll plaza for one week, including pre- and post-festival days. In this study, a spearman correlation matrix between air pollutants and meteorological parameters (temperature, pressure, precipitable water content, relative humidity, and wind speed) were also investigated. The concentration of air pollutants (TSPM, SO2, CO2) and noise were more on the day of festival as the number of vehicles plying on the road was higher in number. Maximum positive correlation was observed between concentration of CO and precipitable water content (Ï â€‰=â€‰0.900) and minimum between SO2 and precipitable water content (Ï â€‰=â€‰0.000). Precipitable water content was positively correlated with all air pollutants (TSPM, NO2, CO, and CO2), and no correlation was observed with SO2. The results show the impact of increase in vehicular movement due to festival on the quality of ambient air and role of meteorology on urban air pollution. Â© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.
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.