Source author record

Mariusz Woźniak

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Majority Edge-Colorings of Graphs

We propose the notion of a majority $k$ -edge-coloring of a graph $G$ , which is an edge-coloring of $G$ with $k$ colors such that, for every vertex $u$ of $G$ , at most half the edges of $G$ incident with $u$ have the same color. We show the best possible results that every graph of minimum degree at least $2$ has a majority $4$ -edge-coloring, and that every graph of minimum degree at least $4$ has a majority $3$ -edge-coloring. Furthermore, we discuss a natural variation of majority edge-colorings and some related open problems.

preprint2022arXiv

On decomposing multigraphs into locally irregular submultigraphs

A locally irregular multigraph is a multigraph whose adjacent vertices have distinct degrees. The locally irregular edge coloring is an edge coloring of a multigraph $G$ such that every color induces a locally irregular submultigraph of $G$ . We say that a multigraph $G$ is locally irregular colorable if it admits a locally irregular edge coloring and we denote by ${\rm lir}(G)$ the locally irregular chromatic index of $G$ , which is the smallest number of colors required in a locally irregular edge coloring of a locally irregular colorable multigraph $G$ . We conjecture that for every connected graph $G$ , which is not isomorphic to $K_2$ , multigraph $^2G$ obtained from $G$ by doubling each edge admits ${\rm lir}(^2G)\leq 2$ . This concept is closely related to the well known 1-2-3 Conjecture, Local Irregularity Conjecture, (2, 2) Conjecture and other similar problems concerning edge colorings. We show this conjecture holds for graph classes like paths, cycles, wheels, complete graphs, complete $k$ -partite graphs and bipartite graphs. We also prove the general bound for locally irregular chromatic index for all 2-multigraphs using our result for bipartite graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.