Repository logo

Browsing by Subject "line graph"

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • thumbnail.journal.alt
    Item type:Article, Access status: Open Access ,
    Edge homogeneous colorings
    (Wydawnictwa AGH, 2022) Madaras, Tomáš; Onderko, Alfréd; Schweser, Thomas
    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.
  • thumbnail.journal.alt
    Item type:Article, Access status: Open Access ,
    Graphs with odd and even distances between non-cut vertices
    (Wydawnictwa AGH, 2025) Antoshyna,Kateryna; Kozerenko, Sergiy
    We prove that in a connected graph, the distances between non-cut vertices are odd if and only if it is the line graph of a strong unique independence tree. We then show that any such tree can be inductively constructed from stars using a simple operation. Further, we study the connected graphs in which the distances between non-cut vertices are even (shortly, NCE-graphs). Our main results on NCE-graphs are the following: we give a criterion of NCE-graphs, show that any bipartite graph is an induced subgraph of an NCE-graph, characterize NCE-graphs with exactly two leaves, characterize graphs that can be subdivided to NCE-graphs, and provide a characterization for NCE-graphs which are maximal with respect to the edge addition operation