×

Incidence coloring of graphs with high maximum average degree. (English) Zbl 1365.05083

Summary: An incidence of an undirected graph G is a pair \((v, e)\) where \(v\) is a vertex of \(G\) and \(e\) an edge of \(G\) incident with \(v\). Two incidences \((v, e)\) and \((w, f)\) are adjacent if one of the following holds: (i) \(v = w\), (ii) \(e = f\) or (iii) \(v w = e\) or \(f\). An incidence coloring of \(G\) assigns a color to each incidence of \(G\) in such a way that adjacent incidences get distinct colors. M. Hosseini Dolama and E. Sopena [Discrete Math. Theor. Comput. Sci. 7, No. 1, 203–216 (2005; Zbl 1153.05318)] proved that every graph with maximum average degree strictly less than 3 can be incidence colored with \(\varDelta + 3\) colors. Recently, M. Bonamy et al. [J. Graph Theory 77, No. 3, 190–218 (2014; Zbl 1304.05042)] proved that every graph with maximum degree at least \(4\) and with maximum average degree strictly less than \(\frac{7}{3}\) admits an incidence \((\varDelta + 1)\)-coloring. In this paper we give bounds for the number of colors needed to color graphs having maximum average degrees bounded by different values between 4 and 6. In particular we prove that every graph with maximum degree at least 7 and with maximum average degree less than 4 admits an incidence \((\varDelta + 3)\)-coloring. This result implies that every triangle-free planar graph with maximum degree at least \(7\) is incidence \((\varDelta + 3)\)-colorable. We also prove that every graph with maximum average degree less than 6 admits an incidence \((\varDelta + 7)\)-coloring. More generally, we prove that \(\varDelta + k - 1\) colors are enough when the maximum average degree is less than \(k\) and the maximum degree is sufficiently large.

MSC:

05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Algor, I.; Alon, N., The star arboricity of graphs, Discrete Math., 75, 11-22 (1989) · Zbl 0684.05033
[2] Bonamy, M.; Lévêque, B.; Pinlou, A., 2-distance coloring of sparse graphs, J. Graph Theory (2014) · Zbl 1304.05042
[3] Brualdi, R. A.; Massey, J. J.Q., Incidence and strong edge colorings of graphs, Discrete Math., 122, 51-58 (1993) · Zbl 0790.05026
[4] Guiduli, B., On incidence coloring and star arboricity of graphs, Discrete Math., 163, 275-278 (1997) · Zbl 0871.05022
[5] Hosseini Dolama, M.; Sopena, E., On the maximum average degree and the incidence chromatic number of a graph, Discrete Math. Theor. Comput. Sci., 7, 203-216 (2005) · Zbl 1153.05318
[6] Hosseini Dolama, M.; Sopena, E.; Zhu, X., Incidence coloring of \(k\)-degenerate graphs, Discrete Math., 283, 121-128 (2004) · Zbl 1064.05057
[7] Jensen, T. R.; Toft, B., Choosability versus chromaticity, Geombinatorics, 5, 45-64 (1995) · Zbl 0855.05055
[8] Maydanskiy, M., The incidence coloring conjecture for graphs of maximum degree 3, Discrete Math., 292, 131-141 (2005) · Zbl 1059.05051
[9] Yang, D., Fractional incidence coloring and star arboricity of graphs, Ars Combin., 105, 213-224 (2012), written in 2007 · Zbl 1274.05183
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.