Multigraph edge-coloring with local list sizes
Let \(G\) be a graph with possibly multiple edges without loops. By \(E_G(v)\) we denote the set of all edges that are incident to a vertex \(v\) in \(G\), by \(E_G(u,v)\) the set of all edges between \(u\) and \(v\) and \(\mu(x,y)=|E_G(u,v)|\) and \(\mu(v)=\max_{z\in V(G)}\mu(v,z)\). An edge coloring is a map \(c:E(G)\rightarrow\{1,\dots,k\}\), \(k\in\mathbb{N}\), such that \(c(e)\neq c(f)\) for any two different edges \(e\) and \(f\) that share at least one vertex. A map \(L:E(G)\rightarrow 2^{\mathbb N}\) is called a list assignment for edges of \(G\). Further, an edge coloring \(c:E(G)\rightarrow \mathbb{N}\) is a proper \(L\)-edge coloring if \(c(e)\in L(e)\) for every \(e\in E(G)\).\N\NThere is a rich history of results of the type that a proper \(L\)-edge coloring exists if the cardinality of \(L(e)\) is bounded from below for each \(e\in E(G)\) by some local condition like some functions on the degrees of the end-vertices of \(e\). This contribution brings a new approach to the mentioned local conditions. For any vertex \(v\) and a list assignment \(L\) the following map is defined: \N\[\Nf(v,L)=\bigcap_{e\in E_G(v)}L(e).\N\]\NWith this new local condition the author proves that \(G\) contains a proper \(L\)-edge coloring in the following cases:\N\begin{itemize}\N\item \(|f(v,L)|\geq \lfloor 3\deg(v)/2 \rfloor\);\N\item \(|f(v,L)|\geq\deg(v)\mu(v)\);\N\item \(G\) is bipartite and \(|f(v,L)|\geq\deg(v)\).\N\end{itemize}
- A Theorem on Coloring the Lines of a Network
- Edge-coloring algorithms for bounded degree multigraphs
- Edge-colouring graphs with local list sizes
- Graph edge coloring. Vizing's theorem and Goldberg's conjecture
- Graph theory
- scientific article; zbMATH DE number 3735847 (Why is no real title available?)
- scientific article; zbMATH DE number 3637904 (Why is no real title available?)
- List edge and list total colourings of multigraphs
- Local version of Vizing's theorem for multigraphs
- On an estimate of the chromatic class of a \(p\)-graph
- The power of multi-step Vizing chains
This page was built for publication: Multigraph edge-coloring with local list sizes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7014508)
