Wyszukiwarka
Abstrakt
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.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Autorzy (4)
-
Carl Johan Casselgren
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
DISCRETE APPLIED MATHEMATICS
nr 372,
strony 23 - 36,
ISSN: 0166-218X - Język:
- angielski
- Rok wydania:
- 2025
- Opis bibliograficzny:
- 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:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2025.03.011
- Źródła finansowania:
-
- Open Access pokryty przez autorów spoza PG
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 0 razy