On coloring the arcs of biregular graphs

DOI10.1016/J.DAM.2020.04.007zbMATH Open1443.05066arXiv1309.7502OpenAlexW3016954600MaRDI QIDQ777426FDOQ777426

Authors: Italo J. Dejter 

Publication date: 7 July 2020

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

Abstract: Recalling each edge of a graph $H$ has 2 oppositely oriented arcs, each vertex $v$ of $H$ is identified with the set of arcs, denoted $(v,e)$, departing from $v$ along the edges $e$ of $H$ incident to $v$. Let $H$ be a $(lambda,mu)$-biregular graph with bipartition $(Y,X)$, where $|Y|=kmu$ and $|X|=klambda$, ($0<k,lambda,muinmathbbZ$). We consider the problem, for each edge $e=yx$ in $H$, of assigning, a color (given by an element) of $Y$, resp. $X$, to the arc $(y,e)$, resp. $(x,e)$, so that each color is assigned exactly once in the set of arcs departing from each vertex of $H$. Furthermore, we set such assignment to fulfill a specific bicolor weight function over a monotonic subset of $YimesX$. This problem applies to the Design of Experiments for Industrial Chemistry, Molecular Biology, Cellular Neuroscience, etc. An algorithmic construction based on biregulzr graphs with bipartitions given by cyclic-group pairs is presented, as well as 3 essentially different solutions to the Great Circle Challenge Puzzle based on a different biregular graph whose bipartition is formed by the vertices and 5-cycles of the Petersen graph.

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

Recommendations

• scientific article; zbMATH DE number 5238183
• On \(b\)-colorings in regular graphs
• On arc-coloring of subcubic graphs
• On interval colourings of bi-regular bipartite graphs
• scientific article; zbMATH DE number 5717278
• Coloring intersection graphs of arc-connected sets in the plane
• Coloring intersection graphs of arcwise connected sets in the plane
• On \(k\)-coloring of weighted circular-arc graphs
• \(b\)-coloring of some bipartite graphs
• scientific article; zbMATH DE number 1008448

zbMATH Keywords

Petersen graphcyclic grouparc coloringbiregular graph

Mathematics Subject Classification ID

Applications of graph theory (05C90) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: On coloring the arcs of biregular graphs

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