Abstract
An incidence in a graph G is a pair (v, e) where v is a vertex of G and e is an edge of G incident to v. Two incidences (v, e) and (u, f) are adjacent if at least one of the following holds: \((a) v = u, (b) e = f\), or \((c) vu \in \{e,f\}\). An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. In this note we prove that every subquartic graph admits an incidence coloring with at most seven colors.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Algor I, Alon N (1989) The star arboricity of graphs. Discret Math 75:11–22
Brualdi RA, Massey JJQ (1993) Incidence and strong edge colorings of graphs. Discret Math 122(1–3):51–58
Clark WE, Dunning LA (1997) Tight upper bounds for the domination numbers of graphs with given order and minimum degree. Electron J Combin 4:R26
Dolama M, Sopena É, Zhu X (2004) Incidence coloring of \(k\)-degenerated graphs. Discret Math 283(1–3):121–128
Fahimi H, Omoomi B (2016) On incidence coloring of some graphs of maximum degree 4. Ars Combin 125:33–45
Gregor P, Lužar B, Soták R (2016) On incidence coloring conjecture in Cartesian products of graphs. Discret Appl Math. doi:10.1016/j.dam.2016.04.030
Guiduli B (1997) On incidence coloring and star arboricity of graphs. Discret Math 163(1–3):275–278
Hall P (1935) On representatives of subsets. J Lond Math Soc 10(1):26–30
Maydanskiy M (2005) The incidence coloring conjecture for graphs of maximum degree 3. Discret Math 292(1–3):131–141
Shiau AC, Shiau TH, Wang YL (2015) Incidence coloring of Cartesian product graphs. Inf Process Lett 115(10):765–768
Sopena, É (2015) The incidence coloring page. http://www.labri.fr/perso/sopena/pmwiki/index.php?n=TheIncidenceColoringPage. Accessed 28 Dec 2015
Acknowledgments
The authors are thankful to the two anonymous referees for their comments that helped improve the presentation of the proof. This research was supported by the Czech Science Foundation Grant GA14–10799S, Slovak VEGA Grant no. 1 / 0368 / 16, and Slovenian Research Agency Program P1–0383. The second author also acknowledges partial support by the National Scholarship Programme of the Slovak Republic.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gregor, P., Lužar, B. & Soták, R. Note on incidence chromatic number of subquartic graphs. J Comb Optim 34, 174–181 (2017). https://doi.org/10.1007/s10878-016-0072-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-016-0072-2