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