Improper interval edge colorings of graphs
| Autor: | Carl Johan Casselgren, Petros A. Petrosyan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Applied Mathematics
Interval edge coloring Improper edge coloring Edge coloring Edge (geometry) Upper and lower bounds Vertex (geometry) Combinatorics Multipartite Datorsystem Integer Computer Systems FOS: Mathematics Bipartite graph Discrete Mathematics and Combinatorics Interval (graph theory) Mathematics - Combinatorics Combinatorics (math.CO) Mathematics |
| Popis: | A k -improper edge coloring of a graph G is a mapping α : E ( G ) ⟶ N such that at most k edges of G with a common endpoint have the same color. An improper edge coloring of a graph G is called an improper interval edge coloring if the colors of the edges incident to each vertex of G form an integral interval. In this paper we introduce and investigate a new notion, the interval coloring impropriety (or just impropriety) of a graph G defined as the smallest k such that G has a k -improper interval edge coloring; we denote the smallest such k by μ int ( G ) . We prove upper bounds on μ int ( G ) for general graphs G and for particular families such as bipartite, complete multipartite and outerplanar graphs; we also determine μ int ( G ) exactly for G belonging to some particular classes of graphs. Furthermore, we provide several families of graphs with large impropriety; in particular, we prove that for each positive integer k , there exists a graph G with μ int ( G ) = k . Finally, for graphs with at least two vertices we prove a new upper bound on the number of colors used in an improper interval edge coloring. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|