On boundaries of extrema of the number of vertices with an interval spectrum on the sets of proper edge t-colorings of some cubic graphs under variation of t

DOI10.12988/IMF.2013.3491zbMATH Open1283.05089arXiv1410.7927OpenAlexW2514644668MaRDI QIDQ5402066FDOQ5402066

Authors: Narine N. Davtyan, Arpine M. Khachatryan, R. R. Kamalian 

Publication date: 12 March 2014

Published in: International Mathematical Forum (Search for Journal in Brave)

Abstract: The sets of vertices and edges of an undirected, simple, finite, connected graph $G$ are denoted by $V(G)$ and $E(G)$, respectively. An arbitrary nonempty finite subset of consecutive integers is called an interval. An injective mapping $varphi:E(G)ightarrow1,2,\mathrm{...},|E(G)|$ is called a labeling of the graph $G$. If $G$ is a graph, $x$ is its arbitrary vertex, and $varphi$ is its arbitrary labeling, then the set $$} is called a spectrum of the vertex $x$ of the graph $G$ at its labeling $varphi$. For any graph $G$ and its arbitrary labeling $varphi$, a structure of the subgraph of $G$, induced by the subset of vertices of $G$ with an interval spectrum, is described.

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

Recommendations

• Estimates for the number of vertices with an interval spectrum in proper edge colorings of some graphs
• On proper edge 3-colorings of a cubic graph
• Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs
• A generalization of interval edge-colorings of graphs
• On one-sided interval edge colorings of biregular bipartite graphs

zbMATH Keywords

cubic graphsedge coloringsinterval spectrum

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cited In (3)

• An exact bound on the number of proper 3-edge-colorings of a connected cubic graph
• On proper edge 3-colorings of a cubic graph
• Estimates for the number of vertices with an interval spectrum in proper edge colorings of some graphs

This page was built for publication: On boundaries of extrema of the number of vertices with an interval spectrum on the sets of proper edge \(t\)-colorings of some cubic graphs under variation of \(t\)

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