Coloring Graphs Without Bichromatic Cycles or Paths
- PDF / 349,149 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 12 Downloads / 213 Views
Coloring Graphs Without Bichromatic Cycles or Paths Jianfeng Hou1 · Hongguo Zhu1 Received: 22 October 2019 / Revised: 11 October 2020 / Accepted: 13 October 2020 © Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia 2020
Abstract Let k ≥ 4 be an integer, and let G be a graph with maximum degree . In 1991, Alon, McDiarmid and Reed proved that G has a proper coloring using O((k−1)/(k−2) ) colors such that G does not have bichromatic paths with k vertices. In this paper, we improve this result by showing G has a proper coloring using (1 + k/21/(k−3) )(k−1)/(k−2) + + 1 colors such that G does not have bichromatic paths with k vertices. We remark that there exists a graph G with maximum degree (k−1)/(k−2) ) colors, there is always such that for any proper coloring of G using ( (log )1/(k−2) a bichromatic path with k vertices. Using the similar method, we also show that G has a proper coloring using O(4/3 ) colors such that G contains neither bichromatic cycles nor bichromatic paths with order 5. Keywords Coloring · Acyclic · Pk -free · Entropy compression Mathematics Subject Classification 05C10 · 05C15
1 Introduction All graphs mentioned in this paper are finite, simple and undirected. For a graph G, we denote its vertex set, edge set and maximum degree of G by V (G), E(G) and (G), respectively. A proper coloring of G is a mapping ϕ: V (G) −→ {1, . . . , k}, such that ϕ(u) = ϕ(v) if uv ∈ E(G). Let k ≥ 4 be an integer. A proper coloring ϕ is called Pk - f r ee if there is no bichromatic path with k-vertices. The Pk - f r ee chr omatic number , denoted by χ Pk (G), is the smallest integer t such that G has a
Communicated by Sanming Zhou. This work is supported by a research grant NSFC(12071077).
B 1
Hongguo Zhu [email protected] Center for Discrete Mathematics, Fuzhou University, Fuzhou 350003, Fujian, China
123
J. Hou, H. Zhu
Pk -free coloring using t colors. We remark that the P4 -free coloring is called the star coloring posed by Fertin, Raspaud and Reed [9], who showed that every graph G with maximum degree admits a star coloring using 203/2 colors. This bound was improved to χs (G) ≤ 4.343/2 by Ndreca, Procacci and Scoppola [14]. For general k ≥ 5, the Pk -free coloring was posed by Alon, McDiarmid and Reed [1], who showed that every graph G with maximum degree has a Pk -free coloring using O((k−1)/(k−2) ) colors. Our first result improves this result by showing Theorem 1.1 Let k ≥ 5 be an integer, and let G be a graph with maximum degree . Then, χ Pk (G) ≤ (1 + k/21/(k−3) )(k−1)/(k−2) + + 1. The following result gives the lower bound on Pk -free chromatic number of graphs. Theorem 1.2 Let k ≥ 5 be an integer. Then, there exists a graph G with maximum degree such that χ Pk (G) ≥ ε
(k−1)/(k−2) , (log )1/(k−2)
where ε is an absolute constant. The Pk -free coloring is closely related to acyclic coloring. Note that a proper coloring of G is acyclic if every cycle has at least 3 colors. The acyclic chromatic number χa (G) of a graph G is the s
Data Loading...
