Edge homogeneous colorings
- 1 January 2022
- journal article
- research article
- Published by AGH University Press in Opuscula Mathematica
- Vol. 42 (1) , 65-73
Abstract
We explore four kinds of edge colorings defined by the requirement of equal number of colors appearing, in particular ways, around each vertex or each edge. We obtain the characterization of graphs colorable in such a way that the ends of each edge see (not regarding the edge color itself) \(q\) colors (resp. one end sees \(q\) colors and the color sets for both ends are the same), and a sufficient condition for 2-coloring a graph in a way that the ends of each edge see (with the omission of that edge color) altogether \(q\) colors. The relations of these colorings to \(M_q\)-colorings and role colorings are also discussed; we prove an interpolation theorem for the numbers of colors in edge coloring where all edges around each vertex have \(q\) colors.
Keywords
This publication has 15 references indexed in Scilit:
- From NMNR-coloring of hypergraphs to homogenous coloring of graphsArs Mathematica Contemporanea, 2017
- On the complexity of role colouring planar graphs, trees and cographsJournal of Discrete Algorithms, 2015
- M_i-edge colorings of complete graphsApplied Mathematical Sciences, 2015
- $M_2$-EDGE COLORING AND MAXIMUM MATCHING OF GRAPHSInternational Journal of Pure and Apllied Mathematics, 2013
- Computing role assignments of chordal graphsTheoretical Computer Science, 2010
- 2-Role assignments on triangulated graphsTheoretical Computer Science, 2003
- How hard is it to determine if a graph has a 2-role assignment?Networks, 2001
- Role colouring a graphMathematical Social Sciences, 1991
- Decomposition of Finite Graphs Into ForestsJournal of the London Mathematical Society, 1964
- Edge-Disjoint Spanning Trees of Finite GraphsJournal of the London Mathematical Society, 1961