Pascal Ochem
-
Negative results on acyclic improper colorings
dmtcs:3441 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3441
Negative results on acyclic improper coloringsConference paper
Authors: Pascal Ochem 1
0000-0001-5504-4586
Pascal Ochem
1 Laboratoire Bordelais de Recherche en Informatique
Raspaud and Sopena showed that the oriented chromatic number of a graph with acyclic chromatic number k is at most k2k−1. We prove that this bound is tight for k≥3. We also show that some improper and/or acyclic colorings are NP-complete on a class C of planar graphs. We try to get the most restrictive conditions on the class C, such as having large girth and small maximum degree. In particular, we obtain the NP-completeness of 3-ACYCLICCOLORABILITY on bipartite planar graphs with maximum degree 4, and of 4-ACYCLICCOLORABILITY on bipartite planar graphs with maximum degree 8.
T. H. Marshall, 2015, An Oriented 6-Coloring of Planar Graphs with Girth at Least 9, Graphs and Combinatorics, 32, 3, pp. 1101-1116, 10.1007/s00373-015-1612-8.
Enqiang Zhu;Zepeng Li;Zehui Shao;Jin Xu;Chanjuan Liu, 2014, Acyclic 3-coloring of generalized Petersen graphs, Journal of Combinatorial Optimization, 31, 2, pp. 902-911, 10.1007/s10878-014-9799-9.
Debajyoti Mondal;Rahnuma Islam Nishat;Md. Saidur Rahman;Sue Whitesides, Lecture notes in computer science, Acyclic Coloring with Few Division Vertices, pp. 86-99, 2012, 10.1007/978-3-642-35926-2_11.
Debajyoti Mondal;Rahnuma Islam Nishat;Sue Whitesides;Md. Saidur Rahman, Lecture notes in computer science, Acyclic Colorings of Graph Subdivisions, pp. 247-260, 2011, 10.1007/978-3-642-25011-8_20.
Daniel Gonçalves;Mickaël Montassier, Lecture notes in computer science, Acyclic Choosability of Graphs with Small Maximum Degree, pp. 239-248, 2005, 10.1007/11604686_21.