Search
Abstract
An interval edge coloring of a graph is a proper edge coloring by integers such that the colors on the edges incident with any vertex form an interval of integers. Not all graphs are interval colorable; a simple counterexample is K3. A near-interval coloring is a proper edge coloring of a graph such that the colors on the edges incident with any vertex is either an interval or a near-interval, where the latter is an interval except for one missing integer. We prove that all graphs of maximum degree at most 4, and all Class 1 graphs of maximum degree 5 and no vertices of degree 3 are near-interval colorable, thereby improving previous results by Petrosyan et al. (2010). We also consider the problem of near-interval coloring outerplanar graphs. For bipartite graphs, we prove that every such multigraph of maximum degree at most 5 admits a near-interval coloring, and that for every ∆ ≥ 18 there is a bipartite graph of maximum degree ∆ with no near- interval coloring. For the case of bipartite multigraphs, we give analogous examples of graphs of maximum degrees ∆ with no near-interval coloring for every ∆ ≥ 15. Finally, we present classes of bipartite multigraphs of maximum degree 6,7 and 8 that admit near-interval colorings.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (4)
-
Carl Johan Casselgren
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
DISCRETE APPLIED MATHEMATICS
no. 372,
pages 23 - 36,
ISSN: 0166-218X - Language:
- English
- Publication year:
- 2025
- Bibliographic description:
- Casselgren C. J., Małafiejski M., Pastuszak K., Petrosyan P.: Near-interval edge colorings of graphs// DISCRETE APPLIED MATHEMATICS -Vol. 372, (2025), s.23-36
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2025.03.011
- Sources of funding:
-
- Open Access pokryty przez autorów spoza PG
- Verified by:
- Gdańsk University of Technology
seen 0 times