Acyclic Coloring of Graphs with Maximum Degree 7
- PDF / 325,843 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 85 Downloads / 169 Views
(0123456789().,-volV) (0123456789().,-volV)
ORIGINAL PAPER
Acyclic Coloring of Graphs with Maximum Degree 7 Juan Wang1,2,3 • Lianying Miao2 • Wenyao Song4 • Yunlong Liu5 Received: 5 November 2019 / Revised: 25 October 2020 / Accepted: 29 October 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract The acyclic chromatic number a(G) of a graph G is the minimum number of colors such that G has a proper vertex coloring and no bichromatic cycles. For a graph G with maximum degree D, Gru¨nbaum (1973) conjectured aðGÞ D þ 1. Up to now, the conjecture has only been shown for D 4. In this paper, it is proved that aðGÞ 12 for D ¼ 7, thus improving the result aðGÞ 17 of Dieng et al. (in: Proc. European conference on combinatorics, graph theory and applications, 2010). Keywords Graph coloring Acyclic coloring Maximum degree Regular graph
Mathematics Subject Classification 05C15
1 Introduction Let G be a graph with vertex set V(G), edge set E(G) and maximum degree D. In this paper, suppose G is finite, simple and connected. A proper k-coloring is a map w : VðGÞ ! f1; 2; . . .; kg such that wðuÞ 6¼ wðvÞ for adjacent vertices u, v. If w This work was partially supported by the National Natural Science Foundation of China (nos. 11771443,12001481 and 12071265) and Shandong Province Natural Science Foundation (no. ZR2017QF011) & Juan Wang [email protected] Lianying Miao [email protected] Wenyao Song [email protected] Yunlong Liu [email protected] Extended author information available on the last page of the article
123
Graphs and Combinatorics
makes no bichromatic cycles in G, then w is called an acyclic k-coloring, and the minimum value of k is the acyclic chromatic number a(G) of G. Acyclic coloring of graphs, first defined by Gru¨nbaum [13], has a wide range of applications such as estimating large and sparse symmetric matrices [5, 14], computing the upper bounds of the track-number of graphs [8], obtaining the cardinality of the minimum feedback vertex set which is an important problem in control theory and computer science [12]. For the acyclic coloring of graphs, Gru¨nbaum [13] gave the two conjectures as follows. Conjecture 1 ([13]) If G is a planar graph, then aðGÞ 5. Conjecture 1 was confirmed by Borodin [4] in 1979. Conjecture 2 ([13]) For every graph G, aðGÞ D þ 1. Conjecture 2 is still an open question except for D 3 [13] and D ¼ 4 [2]. For D ¼ 5, Fertin and Raspaud [11] first showed that aðGÞ 9, then Yadav et al.[23] improved it to aðGÞ 8, later Kostochka and Stocker [17] gave that aðGÞ 7, furthermore, Fiedorowicz [9] proved that Conjecture 2 holds if MadðGÞ 4, where jEðHÞj MadðGÞ ¼maxf2 jVðHÞj : H Gg. Wang et al. [20] recently proved that 7 colors are also sufficient for acyclic list coloring of G with D ¼ 5. For D ¼ 6, Yadav et al. [21] first gave that aðGÞ 12, then Hocquard [15] improved this result to aðGÞ 11, later Zhao et al. [26] proved aðGÞ 10, Wang and Miao [19] recently reduced the number of colors from 10 to 9. In addition, Wang et al. [20] proved th
Data Loading...
