000			03647nam a22002537a 4500
003			ISI Library, Kolkata
005			20240930143854.0
008			240930b |||||||| |||| 00| 0 eng d
040			_aISI Library _bEnglish
082	0	4	_223 _a511.56 _bD779
100	1		_aPattanayak, Drimit _eauthor
245			_aVariants of vertex and edge colorings of graphs/ _cDrimit Pattanayak
260			_aKolkata: _bIndian Statistical Institute, _c2024
300			_a111 pages;
502			_aThesis (Ph.D.)- Indian statistical Institute, 2024
504			_aIncludes conclusion
505	0		_aLinear arboricity of 3-degenerate and 2-degenerate graphs -- Optimal linear coloring of 3-degenerate graphs -- Linear time algorithms -- p-centered colorings of grids
508			_aGuided by Prof. Mathew C. Francis
520			_aA 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) ≤ l ∆(G)+1 2 m where ∆(G) is the maximum degree of G. First, 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 in some classes of graphs like cubic graphs and triangle-free planar graphs for which the conjecture was already known to be true. Next, we prove that for every 2-degenerate graph G, χ ′ l (G) = l ∆(G) 2 m if ∆(G) ≥ 5. We conjecture that this equality holds also when ∆(G) ∈ {3, 4} and show that this is the case for some well-known subclasses of 2-degenerate graphs. All the above proofs can be converted into linear time algorithms that produce linear colorings of input 3-degenerate and 2-degenerate graphs using a number of colors matching the upper bounds on linear arboricity proven for these classes of graphs. Motivated by this, we then show that for every 3-degenerate graph, χ ′ l (G) = l ∆(G) 2 m if ∆(G) ≥ 9. Further, we show that this line of reasoning can be extended to obtain a different proof for the linear arboricity conjecture for all 3-degenerate graphs. This proof has the advantage that it gives rise to a simpler linear time algorithm for obtaining a linear coloring of an input 3-degenerate graph G using at most one more color than the linear arboricity of G. A p-centered coloring of a graph G, where p is a positive integer, is a coloring of the vertices of G in such a way that every connected subgraph of G either contains a vertex with a unique color or contains more than p different colors. As p increases, we get a hierarchy of more and more restricted colorings, starting from proper vertex colorings, which are exactly the 1-centered colorings. Debski, Felsner, Micek and Schroder proved that bounded degree graphs have p-centered colorings using O(p) colors. But since their method is based on the technique of entropy compression, it cannot be used to obtain a description of an explicit coloring even for relatively simple graphs. In fact, they ask if an explicit p-centered coloring using O(p) colors can be constructed for the planar grid. We answer their question by demonstrating a construction for obtaining such a coloring for the planar grid.
650		4	_aGraph theory
650		4	_aColoring of graphs
856			_uhttp://dspace.isical.ac.in:8080/jspui/handle/10263/7465 _yFull Text
942			_2ddc _cTH
999			_c436532 _d436532