Weak-odd chromatic index of special digraph classes
Let \(D=(V(D),A(D))\) be a digraph. A mapping \(\varphi : A(D) \to \{1,\ldots , k\}\) is a weak-odd \(k\)-edge coloring of \(D\) if for any \(v \in V(D)\), there exists \(i \in \{1,\ldots , k\}\) such that the cardinality of sets \(\{vu \in A(D): \varphi(vu)=i\}\) and \(\{uv \in A(D): \varphi(uv)=i\}\) is odd. The minimum \(k\) for which there exists a weak-odd \(k\)-edge coloring of \(D\) is called weak-odd chromatic index of \(D\), denoted by \(\chi_{\textrm{wo}}'(D)\). A tournament is an orientation of a complete graph. A digraph is semicomplete if it is obtained from a complete graph by replacing any edge by the arc of one possible direction or by two arcs corresponding to both directions. An extended tournament is a digraph obtained from a tournament by blowing up some of its vertices into independent sets. The weak-odd chromatic index of a digraph was first studied in [\textit{M. Petruševski} and \textit{R. Škrekovski}, Mat. Bilt. 37, No. 1, 61--74 (2013; Zbl 1348.05090)], where it was proved that \(\chi_{\mathrm{wo}}^\prime (D) \leq 3\) holds for any digraph \(D\). For a digraph \(D\) with \(\chi_{\mathrm{wo}}^\prime (D)=3\), the defect of \(D\), def\((D)\), is the minimum number of vertices \(v\) of \(D\) for which the condition: \(|\{vu \in A(D): \varphi(vu)=i\}|\) and \(|\{uv \in A(D): \varphi(uv)=i\}|\) are odd for some color \(i\), does not hold, where \(\varphi\) is a weak-odd \(k\)-edge coloring. \textit{C. Hernández-Cruz} et al. [Ars Math. Contemp. 22, No. 2, Paper No. 5, 21 p. (2022; Zbl 1493.05103)] characterized tournaments \(T\) with \(\chi_{\mathrm{wo}}^\prime (T) \in \{0,1,2,3\}\) and proved that the defect of \(T\) is one for tournaments \(T\) with \(\chi_{\mathrm{wo}}^\prime (T)=3\). In this paper, the authors consider the same problems for semicomplete digraphs and extended tournaments. They first characterize semicomplete digraphs \(D\) satisfying \(\chi_{\mathrm{wo}}^\prime (D)=k\) for any \(k \in \{0,1,2,3\}\) and show that the defect of a semicomplete digraph \(D\) with \(\chi_{\mathrm{wo}}^\prime (D)=3\) is always 1. Then they characterize extended tournaments \(ET\) with \(\chi_{\mathrm{wo}}^\prime (ET)=k\) for any \(k \in \{0,1,2,3\}\) and prove that also extended tournaments with weak-odd chromatic index 3 have defect equal to 1. Finally, weak-odd edge covering is studied for tournaments. For a digraph \(D\), an edge covering with a color set \(S\) is a mapping that assigns a nonempty subset of \(S\) to any arc of \(D\). The weak-odd edge covering of a digraph is an edge covering that satisfies the weak-odd edge coloring condition for digraphs. In this paper it is proved that any tournament \(T\) with \(\chi_{\mathrm{wo}}^\prime (T)=3\) has a weak-odd 2-edge covering.
- A note on weak odd edge-colorings of graphs
- Classes of directed graphs
- Colouring vertices of plane graphs under restrictions given by faces
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Facial parity edge colouring of plane pseudographs
- Graph theory
- scientific article; zbMATH DE number 426361 (Why is no real title available?)
- Weak-odd edge-coloring of digraphs
This page was built for publication: Weak-odd chromatic index of special digraph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2104925)
