Faculty Publications
Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736
Publications by NITK Faculty
Browse
2 results
Search Results
Item 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)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.