×

Acyclic edge coloring of 2-degenerate graphs. (English) Zbl 1234.05075

Summary: An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number \(k\) such that there is an acyclic edge coloring using \(k\) colors and is denoted by \(a'(G)\). A graph is called 2-degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2-degenerate graphs properly contains series-parallel graphs, outerplanar graphs, non-regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that \(a'(G)\leq\Delta+2\), where \(\Delta = \Delta (G)\) denotes the maximum degree of the graph. We prove the conjecture for 2-degenerate graphs. In fact we prove a stronger bound: we prove that if \(G\) is a 2-degenerate graph with maximum degree \(\Delta \), then \(a'(G)\leq\Delta+1\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ageev, Every circle graph of girth at least 5 is 3-colorable, Discrete Math 195 pp 229– (1999) · Zbl 0934.05054 · doi:10.1016/S0012-365X(98)00192-7
[2] Alon, Acyclic coloring of graphs, Random Struct Alg 2 pp 343– (1991) · Zbl 0735.05036 · doi:10.1002/rsa.3240020303
[3] Alon, Acyclic edge-colorings of graphs, J Graph Theory 37 pp 157– (2001) · Zbl 0996.05050 · doi:10.1002/jgt.1010
[4] Alon, Algorithmic aspects of acyclic edge colorings, Algorithmica 32 pp 611– (2002) · Zbl 1009.68100 · doi:10.1007/s00453-001-0093-8
[5] Amar, All to all wavelength routing in all-optical compounded networks, Discrete Math 235 pp 353– (2001) · Zbl 0977.05132 · doi:10.1016/S0012-365X(00)00289-2
[6] Basavaraju, Acyclic edge coloring of subcubic graphs, Discrete Math 308 pp 6650– (2008) · Zbl 1165.05007 · doi:10.1016/j.disc.2007.12.036
[7] Basavaraju, d-regular graphs of acyclic chromatic index at least d + 2, J Graph Theory 63 pp 226– (2010) · Zbl 1215.05053 · doi:10.1002/jgt.20422
[8] Borodin, Acyclic colorings of planar graphs, Discrete Math 25 pp 211– (1979) · Zbl 0406.05031 · doi:10.1016/0012-365X(79)90077-3
[9] Burnstein, Every 4-valent graph has an acyclic five-coloring, Soobsč Akad Nauk Gruzin SSR 93 pp 21– (1979)
[10] Card, Acyclic edge-colorings of sparse graphs, Appl Math Lett 7 pp 63– (1994) · Zbl 0796.05032 · doi:10.1016/0893-9659(94)90055-8
[11] Diestel, Graph Theory 173 (2000)
[12] Fiamcik, The acyclic chromatic class of a graph, Math Slovaca 28 pp 139– (1978) · Zbl 0388.05015
[13] Gerke, Generalised acyclic edge colourings of graphs with large girth, Discrete Math 307 pp 1668– (2007) · Zbl 1118.05034 · doi:10.1016/j.disc.2006.09.004
[14] Greenhill, Bounds on the generalised acyclic chromatic numbers of bounded degree graphs, Graphs Combin 21 pp 407– (2005) · Zbl 1090.05025 · doi:10.1007/s00373-005-0635-y
[15] Grünbaum, Acyclic colorings of planar graphs, Israel J Math 14 pp 390– (1973) · Zbl 0265.05103 · doi:10.1007/BF02764716
[16] Kostochka, Acyclic and oriented chromatic numbers of graphs, J Graph Theory 24 pp 331– (1997) · Zbl 0873.05044 · doi:10.1002/(SICI)1097-0118(199704)24:4<331::AID-JGT5>3.0.CO;2-P
[17] M. Molloy B. Reed Further algorithmic aspects of Lovász local lemma 524 529 · Zbl 1028.68105
[18] Muthu, Improved bounds on acyclic edge coloring, Elect Notes Discrete Math 19 pp 171– (2005) · Zbl 1203.05058 · doi:10.1016/j.endm.2005.05.024
[19] Muthu, Lecture Notes in Computer Science, in: Proceedings of the 12th International Conference, COCOON pp 360– (2006) · Zbl 1162.05317 · doi:10.1007/11809678_38
[20] Muthu, Lecture Notes in Computer Science, in: Algorithmic Aspects in Information and Management pp 144– (2007) · Zbl 1137.68499 · doi:10.1007/978-3-540-72870-2_14
[21] R. Muthu N. Narayanan C. R. Subramanian 2008 http://www.imsc.res.in/narayan/p2t.pdf
[22] Něsetřil, The acyclic edge chromatic number of a random d-regular graph is d + 1, J Graph Theory 49 pp 69– (2005) · Zbl 1062.05062 · doi:10.1002/jgt.20064
[23] Skulrattankulchai, Acyclic colorings of subcubic graphs, Inf Process Lett 92 pp 161– (2004) · Zbl 1169.05325 · doi:10.1016/j.ipl.2004.08.002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.