Please use this identifier to cite or link to this item:
http://hdl.handle.net/10263/7465
Title: | Variants of vertex and edge colorings of graphs |
Authors: | Pattanayak, Drimit |
Keywords: | Variants of vertex Colorings of graphs Linear arboricity Graph coloring Centered colorings Linear colorings |
Issue Date: | Jul-2024 |
Publisher: | Indian Statistical Institute, Kolkata |
Citation: | 112p. |
Series/Report no.: | ISI Ph. D Thesis;TH |
Abstract: | 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) ≤ 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. |
Description: | This thesis is under the supervision of Prof. Mathew C. Francis |
URI: | http://hdl.handle.net/10263/7465 |
Appears in Collections: | Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
thesis-Drimit Pattanayak-5-9-24.pdf | Thesis | 1.1 MB | Adobe PDF | View/Open |
Form17-Drimit- Pattanayak.pdf | Form-17 | 200.78 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.