Faculty Publications
Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736
Publications by NITK Faculty
Browse
3 results
Search Results
Item 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.Item 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.Item An improved upper bound for the domination number of a graph(Springer, 2025) Arumugam, S.; Hegde, S.M.; Kulamarva, S.Let G be a graph of order n. A classical upper bound for the domination number of a graph G having no isolated vertices is ?n2?. However, for several families of graphs, we have ?(G)??n? which gives a substantially improved upper bound. In this paper, we give a condition necessary for a graph G to have ?(G)??n?, and some conditions sufficient for a graph G to have ?(G)??n?. We also present a characterization of all connected graphs G of order n with ?(G)=?n?. Further, we prove that for a graph G not satisfying rad(G)=diam(G)=rad(G¯)=diam(G¯)=2, deciding whether ?(G)??n? or ?(G¯)??n? can be done in polynomial time. We conjecture that this decision problem can be solved in polynomial time for any graph G. © Indian Academy of Sciences 2025.