Improper interval edge colorings of graphs

DOI10.1016/J.DAM.2021.08.038MaRDI QIDQ2235270zbMATH OpenOpenAlexFDO

Authors Carl Johan Casselgren, P. A. Petrosyan

Publication date 21 October 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2003.06166

zbMATH Keywords

edge coloringimproper edge coloringinterval edge coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A $k$-improper edge coloring of a graph $G$ is a mapping $alpha:E(G)longrightarrowmathbbN$ 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 $m{u}_{mathrmint}(G)$. We prove upper bounds on $m{u}_{mathrmint}(G)$ for general graphs $G$ and for particular families such as bipartite, complete multipartite and outerplanar graphs; we also determine $m{u}_{mathrmint}(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 $m{u}_{mathrmint}(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.

Recommendations

• On improper interval edge colourings.
• A note on upper bounds for the maximum span in interval edge-colorings of graphs
• Improper C-colorings of graphs
• Estimates for the number of vertices with an interval spectrum in proper edge colorings of some graphs
• A generalization of interval edge-colorings of graphs

Cites work

• Compact scheduling of zero-one time operations in multi-stage systems
• Consecutive colorings of the edges of general graphs
• Consecutive edge-coloring of the generalized -graph
• Defective and clustered graph colouring
• scientific article; zbMATH DE number 3979083 (Why is no real title available?)
• scientific article; zbMATH DE number 4008419 (Why is no real title available?)
• scientific article; zbMATH DE number 165470 (Why is no real title available?)
• scientific article; zbMATH DE number 1194938 (Why is no real title available?)
• scientific article; zbMATH DE number 1161387 (Why is no real title available?)
• scientific article; zbMATH DE number 1990715 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 3428958 (Why is no real title available?)
• scientific article; zbMATH DE number 6472631 (Why is no real title available?)
• Interval colorings of edges of a multigraph
• Interval edge colorings of some products of graphs
• Interval non-edge-colorable bipartite graphs and multigraphs
• Investigation on interval edge-colorings of graphs
• On improper interval edge colourings.
• On interval colourings of bi-regular bipartite graphs
• On interval edge colorings of biregular bipartite graphs with small vertex degrees
• On the chromatic index of outerplanar graphs
• On the deficiency of bipartite graphs

Cited in

(8)

• Interval non-total colorable graphs
• Improper interval graphs and the corresponding minimal forbidden interval subgraphs
• On improper interval edge colourings.
• Stability of critical p-improper interval graphs
• \(\delta^{(k)}\)-colouring of cycle related graphs
• Improper C-colorings of graphs
• On improper interval colorings of complete multipartite graphs
• The interval coloring impropriety of planar graphs

This page was built for publication: Improper interval edge colorings of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2235270)